python - 如何通过提前检测边界情况来减少递归时间

Question

例如，教科书中的代码——使用递归解决斐波那契问题——是这样的：

cache = {}

def fibo(n):
    if n in cache :
        return cache[n]
    elif n <=2:
        cache[n] = 1
    else:
        cache[n] = fibo(n-1) + fibo(n-2)
    return cache[n]

但是，我担心每次进行函数调用时都需要成本。为什么教科书不使用这段代码，以避免不必要的函数调用：

cache = {}

def fibo(n):
    if n <=2:
        cache[n] = 1
    else:
        # to avoid unnecessary function call
        if n-1 in cache:
            f1 = cache[n-1]
        else:
            f1 = fibo(n-1)
        if n-2 in cache:
            f2 = cache[n-2]
        else:
            f2 = fibo(n-2)

        cache[n] = f1 + f2

    return cache[n]

这样，我们可以在实际调用之前避免不必要的函数调用。

无论如何，我的问题是，为什么教科书的作者不使用第二种方式编写代码？

Answer 1

您所描述的是动态编程。您正在使用一个数组来存储递归的步骤，ala memoization。对于像斐波那契这样的东西，每次迭代有不止一个递归调用，动态编程确实是首选技术。

至于为什么教科书向您展示了它所做的代码，很可能是因为作者只想演示递归，而不是一次涉及太多概念。