Fibonacci

Fibonacci sequence is a series in the following sequence                                                          It can be easily seen from the above sequence that it is following this recurrence relation :

    

Making a program of Fibonacci series is really easy. Here we will discuss to make Fibonacci series using iterative method and recursion.

Iterative Method

In this method we simply store the previous two values in two variables and use

  to calculate next value.

Recursive Method

We normally do not use recursion to find Fibonacci numbers because if we do so, we calculate each value again and again.

function fib(n)
       if n <=1 return n
       return fib(n − 1) + fib(n − 2) 

Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Finding same values again and again is not a good option. Therefore we do not use recursion.
Here is the program using recursion