递归实现Fib数列：调用fib(10)时fib(4)被计算多少次？

给定递归实现的斐波那契函数：

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

要计算调用fib(10)时fib(4)被执行的次数，我们可以通过递推逻辑分析：

• 定义count(m)为调用fib(m)时fib(4)的调用次数：
  • 当m == 4时，count(4) = 1（直接调用1次）
  • 当m < 4时，count(m) = 0（不会触发fib(4)的调用）
  • 当m > 4时，count(m) = count(m-1) + count(m-2)（因为fib(m)会调用fib(m-1)和fib(m-2)，fib(4)的总次数是这两个子调用中次数的总和）

按照递推关系逐步计算：

• count(5) = count(4) + count(3) = 1 + 0 = 1
• count(6) = count(5) + count(4) = 1 + 1 = 2
• count(7) = count(6) + count(5) = 2 + 1 = 3
• count(8) = count(7) + count(6) = 3 + 2 = 5
• count(9) = count(8) + count(7) = 5 + 3 = 8
• count(10) = count(9) + count(8) = 8 + 5 = 13

最终结论：调用fib(10)时，fib(4)会被计算13次。

内容的提问来源于stack exchange，提问作者SaggySav