algorithm - 如果删除 "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 开头的斐波那契数列。也可以为它计算一个封闭形式的表达式。