我在
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)
请注意最后一条语句 – 它与条目调用相同.如果程序此时结束,它将始终以递归方式执行.
总是检查你将如何逃避递归,顺便说一句,检查你的“新改进版本”.