CodeChrist - This is a personal blog which I write to help follow coders

If you like it, feel free to comment and appreciate the good work


Following are the some features of CodeChrist

  • Easy to navigate and use.
  • You can subscibe for emails
  • CodeChrist is beautiful on every screen size (try resizing your browser!)
by

Fibonacci

Fibonacci sequence is a series in the following sequence0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\;                                                          It can be easily seen from the above sequence that it is following this recurrence relation :
F_n = F_{n-1} + F_{n-2},\!\,    
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
 F_n = F_{n-1} + F_{n-2},\!\, 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

0 comments:

Post a Comment