Data Structures and Algorithms - Old Questions

4. Write recursive algorithm to get Fibonacci term. Illustrate it drawing recursion tree.

A Fibonacci sequence is the sequence of integer in which each element in the sequence is the sum of the two previous elements.

Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.

       Fn = Fn-1 + Fn-2

E.g.

F8 = 0,  1,  1,  2,  3,   8,  13  or, F8 = 1,  1,  2,  3,  5,  8,  13,  21

Recursive algorithm to get Fibonacci sequence:

1. START

2. Input the non-negative integer ‘n’

3. If (n==o || n==1)

        return n;

    else

        return fib(n-1)+fib(n-2);

4. Print, nth Fibonacci number

5. END