我刚在接受记者采访时这个问题，不知道怎么算出答案。 有多少额外的函数调用并FIB（n）的要求，如果LINE 3被删除？答案应该是无论在n个。

  INT FIB（INT N）{
  如果（N == 0）返回0;
  如果（N == 1）返回1;
  如果（N == 2）返回1; //行3此处＆lt; ---

  返回FIB（N  -  1）+ FIB（N  -  2）;
}
 

解决方案

它可以很容易地计算出来。旧的code：

 来（0）=（1）=（2）= 1
到（n）=到（n-1）+到（n + 2）+1
 

新的code：

  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-（到（N-1）+到（n + 2）1）
    =（TN（N-1）-TO（N-1））+（TN（N-2）-TN（N-2））+（1-1）
    = D（N-1）+ D（n-2个）
 

这意味着差为Fibonacci序列与0,0,2开始。另外，也可以计算出一个封闭的形式的前pression它

I just got this question on an interview and had no idea how to calculate the answer. How many additional function calls does fib(n) require if "LINE 3" is removed? The answer should be in terms on 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);
}

It can be easily calculated. The old code:

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

The new code:

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

The difference is computed simply by subtracting those two:

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)

Which means the difference is a Fibonacci sequence beginning with 0,0,2. It is also possible to calculate a closed form expression for it.