python – 有人可以解释为什么这会修复我的递归错误吗?
发布时间:2020-12-16 23:21:30 所属栏目:Python 来源:网络整理
导读:我在 Python中递归地实现二进制搜索(我知道这很糟糕)并且使用以下代码获得了最大递归错误: def bs_h(items,key,lower,upper): if lower == upper: return None mid = (lower + upper) // 2 if key items[mid]: return bs_h(items,mid) else: return bs_h(it
我在
Python中递归地实现二进制搜索(我知道这很糟糕)并且使用以下代码获得了最大递归错误:
def bs_h(items,key,lower,upper): if lower == upper: return None mid = (lower + upper) // 2 if key < items[mid]: return bs_h(items,mid) else: return bs_h(items,mid,upper) def bs(items,key): return bs_h(items,len(items)-1) 然后我改变了我的参数和基本情况,如下所示: def bs_h(items,upper): if lower + 1 == upper: return None mid = (lower + upper) // 2 if key < items[mid]: return bs_h(items,-1,len(items)) 这修复了错误,但我不确定原因.有人可以解释一下吗? 解决方法
无论何时使用递归(并且它有时非常有用),您都需要非常小心结束条件.
>它会终止吗? 在代码运行期间的某个时刻,您可能会调用以下内容: bs_h(items,10,11) 然后导致: mid = (lower + upper) // 2 = (10 + 11) // 2 = 10 if key < items[10]: return bs_h(items,10) else: return bs_h(items,11) 请注意最后一条语句 – 它与条目调用相同.如果程序此时结束,它将始终以递归方式执行. 总是检查你将如何逃避递归,顺便说一句,检查你的“新改进版本”. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |