python - 有人可以解释为什么这会修复我的递归错误吗？

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)

请注意最后一条语句 - 它与入口调用相同。如果程序在此时结束，它将始终递归执行。

始终检查您将如何从递归中逃脱，顺便说一句，为此检查您的“新改进版本”。