如果删除"LINE 3",fib(n)需要多少额外的函数调用？

Question

我在面试时得到了这个问题,不知道如何计算答案.
如果删除"LINE 3",fib(n)需要多少额外的函数调用？答案应该是n.

int fib(int n) {
  if(n == 0) return 0;
  if(n == 1) return 1;
  if(n == 2) return 1; //LINE 3 HERE <---

  return fib(n - 1) + fib(n - 2);
}

Answer 1

它很容易计算出来.旧代码:

TO(0)=TO(1)=TO(2)=1
TO(n)=TO(n-1)+TO(n+2)+1

新代码:

TN(0)=TN(1)=1
TN(n)=TN(n-1)+TN(n-2)+1

简单地通过减去这两个来计算差异:

D(0)=D(1)=0
D(2)=3-1=2
D(n)=TN(n)-TO(n)=TN(n-1)+TN(n-2)+1-(TO(n-1)+TO(n+2)+1)
    =(TN(n-1)-TO(n-1))+(TN(n-2)-TN(n-2))+(1-1)
    =D(n-1)+D(n-2)

这意味着差异是从0,0,2开始的斐波那契序列.也可以为它计算闭合表格表达式.