Question

The Fibonacci sequence is series of integers.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

observe the pattern? Each element in the series is the sum of preceding 2 elements. Here is a recursive method for calculating the nth number of the sequence-

Fib (N) = {N, if N=0or 1
Fib (N-2) +Fib (N-1), if N>1

a. write down a recursive method Fibonacci that returns the nth Fibonacci number when passed the argument n.

b. write down a non-recursive version of the process Fibonacci.

c. write down a driver to test your 2 version of the method Fibonacci.

d. evaluate the recursive and iterative version for efficiency.