Question

Complete computefibonacci() to return fn, where f0 is 0, f1 is 1, f2 is 1, f3 is 2, f4 is 3, and continuing: fn is fn-1 + fn-2. hint: base cases are n == 0 and n == 1.

Answer 1

Answer:

Fibonacci series is given by

f(0)=0, f(1)=1, f(2)=1, f(3)=2, f(4)=3.....

As you can see using the above result

f(4)=f(3) + f(2),

f(3)=f(2) + f(1),

f(2)=f(1) + f(0)

Proceeding using same pattern

f(5)=f(4) + f(3)=3+2=5

f(6)=f(4) + f(5)=3+5=8

f(7)=f(6) + f(5)=8+5=13

f(8)=f(7) + f(6)=13+8=21

f(9)=f(8) + f(7)= 21+13=34

f(10)=f(9) + f(8)=34+21=55

...........................................

..........................................

f(n-2)=f(n-3)  + f(n-4)

f(n-1)=f(n-2)+ f(n-3)

Similarly and finally we get using the same pattern we get, As given f(n)=f(n-1) + f(n-2).