对于 fib(n)，假设 c < n, and the implementation of fib is unoptimized with hashmap?

Question

假设我的 fibbonacci 实现是没有 hashMap 的递归未优化版本，那么如果我想计算 fibbonacci(100) ，我如何从数学上找到 fibbonacci(3) 会被调用多少次？ 我知道以编程方式，只需使用计数器即可找到它。

Answer 1

令 g(n,c) 表示所需数量。现在我们知道 fib(1)=1，因此在计算 fib(n) 时，调用 fib(1) 的次数等于 fib(n)。即g(n,1)=fib(n)。现在 fib(1) 被 fib(2) 和 fib(3) 调用。所以 g(n,1) = g(n,2)+g(n,3)。现在这就像一个反向斐波那契序列，从 n 开始，然后向 0 增长。因此，g(n,c) 只是 fib(n,n-c+1)。