Fibonacci numbers are computed using the following recursive

Fibonacci numbers are computed using the following recursive function.

int Fibonacci(int N)

{

if (N == 0 || N == 1) return N;

else

return Fibonacci(N-1) + Fibonacci(N-2);

}

a. Show the steps to compute Fibonacci(6)

b. What is the recurrence relation for the runtime for Fibonacci(N)

Solution

Fibonacci numbers are computed using the following recursive function.
int Fibonacci(int N)
{
if (N == 0 || N == 1) return N;
else
return Fibonacci(N-1) + Fibonacci(N-2);
}
a. Show the steps to compute Fibonacci(6)
Fibonacci(6)
= Fibonacci(5) + Fibonacci(4)
= Fibonacci(4) + Fibonacci(3) + Fibonacci(4)
= Fibonacci(3) + Fibonacci(2) + Fibonacci(3) + Fibonacci(4)
= Fibonacci(2) + Fibonacci(1) + Fibonacci(2) + Fibonacci(3) + Fibonacci(4)
= Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(2) + Fibonacci(3) + Fibonacci(4)
= 1 + Fibonacci(0) + Fibonacci(1) + Fibonacci(2) + Fibonacci(3) + Fibonacci(4)
= 1 + 0 + Fibonacci(1) + Fibonacci(2) + Fibonacci(3) + Fibonacci(4)
= 1 + 0 + 1 + Fibonacci(2) + Fibonacci(3) + Fibonacci(4)
= 1 + 0 + 1 + Fibonacci(1) + Fibonacci(0) + Fibonacci(3) + Fibonacci(4)
= 1 + 0 + 1 + 1 + Fibonacci(0) + Fibonacci(3) + Fibonacci(4)
= 1 + 0 + 1 + 1 + 0 + Fibonacci(3) + Fibonacci(4)
= 1 + 0 + 1 + 1 + 0 + Fibonacci(2) + Fibonacci(1) + Fibonacci(4)
= 1 + 0 + 1 + 1 + 0 + Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(4)
= 1 + 0 + 1 + 1 + 0 + 1 + Fibonacci(0) + Fibonacci(1) + Fibonacci(4)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + Fibonacci(1) + Fibonacci(4)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + Fibonacci(4)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + Fibonacci(3) + Fibonacci(2)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + Fibonacci(2) + Fibonacci(1) + Fibonacci(2)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + Fibonacci(1) + Fibonacci(0) + Fibonacci(1) + Fibonacci(2)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + Fibonacci(0) + Fibonacci(1) + Fibonacci(2)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + Fibonacci(1) + Fibonacci(2)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + Fibonacci(2)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + Fibonacci(1) + Fibonacci(0)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1 + Fibonacci(0)
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 1 + 0 = 8

b. What is the recurrence relation for the runtime for Fibonacci(N)
The recurrence relation is:
Fibonacci(N) = Fibonacci(N-1) + Fibonacci(N-2) if N > 1
Fibonacci(N) = N if N ==1 or N == 0