递归函数没有返回？

Question

我编写了以下函数来实现我自己的二分查找

def bisect(input, target):
    mid = len(input)/ 2
    if len(input) == 1:
        if input[0] == target:
            return 1
        else:
            return None
    elif input[mid] > target:
        bisect(input[:mid], target)
    elif input[mid] <= target:
        bisect(input[mid:], target)

我知道我的实现已经关闭，但我对理解这里的递归堆栈更加好奇。

当我调用时bisect(['d','e'], 'd')，我的函数应该返回

bisect(['d'], 'd')

但它返回无。此外，当我bisect(['d'], 'd')直接调用时 ，我得到了正确的 0 值。这怎么可能？

Answer 1

您忽略了递归调用的返回值。您也需要明确返回这些：

elif input[mid] > target:
    return bisect(input[:mid], target)
elif input[mid] <= target:
    return bisect(input[mid:], target)

递归调用就像任何其他函数调用一样；他们将结果返回给调用者。如果你忽略返回值，然后调用函数结束，你最终会得到那个调用函数然后返回None。