有人可以解释为什么这解决了我的递归错误？

Question

我是在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,key, lower, mid) 
    else: 
     return bs_h(items,key,mid,upper) 

def bs(items,key): 
    return bs_h(items,key, 0, len(items)-1) 

然后我改变了我的参数和基本情况，像这样：

def bs_h(items,key,lower,upper): 
    if lower + 1 == upper: 
     return None 
    mid = (lower + upper) // 2 
    if key < items[mid]: 
     return bs_h(items,key, lower, mid) 
    else: 
     return bs_h(items,key,mid,upper) 

def bs(items,key): 
    return bs_h(items,key, -1, len(items)) 

这解决了错误，但我不知道为什么。有人可以解释吗？

Answer 1

无论何时使用递归（有时非常有用），您需要注意极端的有关结束条件。

1. 它终止吗？
2. 如果有，它会有多深？

在你的代码的运行过程中的某个时刻，你可能有这样一个电话：

bs_h(items, key, 10, 11) 

然后导致：

mid = (lower + upper) // 2 
    = (10 + 11) // 2 
    = 10 
if key < items[10]: 
    return bs_h(items, key, 10, 10) 
else: 
    return bs_h(items, key, 10, 11) 

注意最后一句话 - 这是相同的作为入场通话。如果程序在此时结束，它将始终以递归方式运行。

总是检查你如何摆脱递归，顺便说一句，检查你的“新的改进版本”。

Answer 2

什么修复你的代码是这样的变化：

if lower + 1 == upper: 
    return None 

的变化bs是无关紧要的（至少对于这个目的，我真的反对它）。

的原因可以从下面的实验中观察到：

>>> (0+0)//2 
0 

>>> (0+1)//2 
0 

因此，中点不会改变一次的时间间隔为< = 1，因此它遵循你应该尽早停止，否则你将继续循环等待中点改变，永远不会发生。

Answer 3

将一个print(lower, upper, mid)声明您mid = (lower + upper) // 2语句后您的第一个bs_h例子，注意以下事项：

>>> bs(list(range(10)), 5) 
0 9 4 
4 9 6 
4 6 5 
5 6 5 
5 6 5 
... # repeats until max recursion depth. 

由于两个(n+n)//2和(n+n+1)//2都是一样的，你到一个地步，你连续调用bs_h相同的lower和upper参数。 您应该调整后续调用以消除边界条件（已经被选中）。你还需要返回类似索引的东西。以下你想要的递归模式匹配，并返回正确的索引：

def bs_h(items,key,lower,upper): 
    if lower > upper: 
     return None 
    mid = (lower + upper) // 2 
    if key < items[mid]: 
     return bs_h(items,key, lower, mid-1) 
    elif key > items[mid]: 
     return bs_h(items,key,mid+1,upper) 
    else: 
     return mid #Found! return index 

而且测试：

>>> for i in range(10): 
    print(bs(list(range(10)), i)) 

0 
1 
2 
3 
4 
5 
6 
7 
8 
9 

>>> print(bs(list(range(10)), 4.5)) 
None 

>>> print(bs(list(range(10)), 100000)) 
None 

Answer 4

格伦Rogeres是正确的。 但是，为了确保事情都没有错过，

• 首先，它的二进制搜索 - 这意味着要找到一个排序列表值。
• 你可以检查后（一旦 元素被发现在你的情况，mid变量！）返回元素的索引
• 如果关键是<或>比项目[MID]你可以忽略中期在你的下一个递归搜索元素（MID-1或中期+ 1）

也就是说，

def bs_h(items,key,lower,upper): 
    if lower>upper:return None 
    mid = (lower + upper)// 2 
    if key < items[mid]: 
     return bs_h(items,key, lower, mid-1) 
    elif key > items[mid]: 
     return bs_h(items,key, mid+1, upper) 
    else:return mid 

def bs(items,key): 
    return bs_h(sorted(items),key, 0, len(items)-1)