3

我有两个函数fib1来fib2计算斐波那契。

def fib1(n):
    if n < 2:
        return 1
    else:
        return fib1(n-1) + fib1(n-2)

def fib2(n):
    def fib2h(s, c, n):
        if n < 1:
            return s
        else:
            return fib2h(c, s + c, n-1)
    return fib2h(1, 1, n)

fib2工作正常，直到它破坏递归限制。如果理解正确，Python 不会针对尾递归进行优化。这对我来说很好。

让我感到惊讶fib1的是，即使n. 为什么会这样？为什么它在变得迟缓之前没有达到递归限制？

4

3 回答 3

6

基本上，您通过反复计算相同的 n 值的 fib1 来浪费大量时间。您可以像这样轻松地记住函数

def fib1(n, memo={}):
    if n in memo:
        return memo[n]
    if n < 2:
        memo[n] = 1
    else:
        memo[n] =  fib1(n-1) + fib1(n-2)
    return memo[n]

您会注意到我使用空字典作为默认参数。这通常是一个坏主意，因为每个函数调用都使用相同的 dict 作为默认值。

在这里，我利用它来记忆我计算的每个结果

您还可以使用 0 和 1 来初始化备忘录以避免需要n < 2测试

def fib1(n, memo={0: 1, 1: 1}):
    if n in memo:
        return memo[n]
    else:
        memo[n] =  fib1(n-1) + fib1(n-2)
    return memo[n]

变成

def fib1(n, memo={0: 1, 1: 1}):
    return memo.setdefault(n, memo.get(n) or fib1(n-1) + fib1(n-2))
于 2012-10-11T00:28:45.547 回答
5

你的问题不是python，而是你的算法。fib1是树递归的一个很好的例子。你可以在 stackoverflow上找到这个特定算法是 (~ ) 的证明。θ(1.6n)

n=30（显然来自评论）大约需要三分之一秒。如果计算时间扩大为1.6^n，我们预计n=100需要大约210 万年。

于 2012-10-11T00:12:55.193 回答
2

想想每个中的递归树。第二个版本是递归的单个分支，在函数调用的参数计算中进行添加，然后返回值。正如您所指出的，Python 不需要尾递归优化，但如果尾调用优化是您的解释器的一部分，则也可以触发尾递归优化。

另一方面，第一个版本在每个级别都需要 2 个递归分支！因此，该函数的潜在执行次数大幅增加。不仅如此，大部分工作还要重复两次！考虑：fib1(n-1)最终fib1(n-1)再次调用，这与fib1(n-2)从第一个调用帧的参考点调用相同。但是在计算出那个值之后，它必须fib1(n-2)再次加到 的值上！因此，这项工作被不必要地重复了很多次。

于 2012-10-11T00:09:48.613 回答