有人能解释一下为什么这会修复我的递归错误吗？

Question

我在Python中递归地实现二进制搜索（我知道这很糟糕），得到了一个max递归错误，代码如下：

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

在第一个bs_h示例中的mid = (lower + upper) // 2语句后面放一个print(lower, upper, mid)语句，并观察以下内容：

>>> 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总是相同的，所以您可以使用相同的lower和upper参数连续调用bs_h。 您应该调整后续调用以消除边界条件（已经检查过）。您还需要返回索引之类的内容。以下内容与所需的递归模式匹配，并返回正确的索引：

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 2

无论何时使用递归（有时非常有用），都需要非常小心结束条件。你知道吗

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)

注意最后一个语句-它与entry调用相同。如果程序在这一点结束，它总是递归地运行。你知道吗

总是检查你将如何从递归中逃脱，顺便说一句，检查你的“新的改进版本”。你知道吗

Answer 3

修复代码的是以下更改：

if lower + 1 == upper:
    return None

在bs中的变化是不相关的（至少在这个目的上，我会反对它）。你知道吗

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

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

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

因此，一旦间隔为<；=1，中点就不会改变，因此您应该尽早停止，否则您将继续循环等待中点改变，这是永远不会发生的。你知道吗