斐波那契数列的递归问题

Question

我需要帮助理解此处的处理过程，假设我调用fib（5），我想要的是斐波那契数列的第5个数，也就是8。但是我的大脑试图理解这个算法，却觉得答案不是这样的。下面是我错误地想到的：

return fib(4) + fib(3) // Stack frame 1
return fib(3) + fib(1) // Stack frame 2

现在因为x等于1，即fib(1)，条件语句if x == 0 or x == 1:导致递归结束。根据我的逻辑，���将变成3+1+4+3。请纠正我的错误逻辑。

def fib(x):
    """assumes x an int >= 0
       returns Fibonacci of x"""
    assert type(x) == int and x >= 0
    if x == 0 or x == 1:
        return 1
    else:
        return fib(x-1) + fib(x-2)

- Tom Lilletveit

---

只需在纸上写下第一个调用，并将函数的每个递归调用替换为有效的返回语句。 你可能不理解的是，return fib(x - 1) + fib( x - 2) 会两次调用你的fib函数，一次使用参数x = 当前x减少一次，另一次减少两次。当使用函数时，这是一个典型的误解，因此您可能还应该再次查看函数参数。 - Jean-Marie Comets

只需在您的函数中添加一些打印语句并运行它，就可以看到它的执行过程了。 - martineau

Answer 1

以下是全部内容的详细扩展：

fib(5) expands to fib(4)+fib(3)
  fib(4) expands to fib(3)+fib(2)
    fib(3) expands to fib(2)+fib(1)
      fib(2) expands to fib(1)+fib(0)
        fib(1) evaluates to 1
        fib(0) evaluates to 1
      fib(1) evaluates to 1
    fib(2) expands to fib(1)+fib(0)
      fib(1) evaluates to 1
      fib(0) evaluates to 1
  fib(3) expands to fib(2)+fib(1)
    fib(2) expands to fib(1)+fib(0)
      fib(1) evaluates to 1
      fib(0) evaluates to 1
    fib(1) evaluates to 1

如果你数一下，答案就是8。

- NPE

Answer 2

对于大于 1 的所有 x，fib 函数会调用自身两次:

1. fib(5) 变成 fib(4) + fib(3)
2. 然后扩展到 (fib(3) + fib(2)) + (fib(2) + fib(1))
3. 再扩展到 ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1)
4. 再扩展到 (((fib(1) + fib(0)) + 1) + (1 + 1)) + ((1 + 1) + 1)
5. 最终扩展成 (((1 + 1) + 1) + (1 + 1)) + ((1 + 1) + 1)

这总和为 8。

- Martijn Pieters