Menu
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);
}
859
That is, the number of function calls to calculate a Fibonacci number F(n) is 2F(n)−1.
If we call Fibonacci(4) , the recursive function is called five times: the initial call, the three times just mentioned for n=3 , and one more recursive call with n=2 . Computing Fibonacci(5) makes a total of nine calls, and Fibonacci(6) makes a total of 9+5+1=15 calls.
The 12th and the 13th term of the Fibonacci sequence are 89 and 144.
What is Fibonacci Sequence Formula in Math? The Fibonacci sequence formula deals with the Fibonacci sequence, finding its missing terms. The Fibonacci formula is given as, Fn = Fn-1 + Fn-2, where n > 1.
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.
141
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
