Fibonacci Series - Data Structures and Algorithms

Fibonacci series generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers − F0 & F1. The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.

Fibonacci series satisfies the following conditions:

 

Fn = Fn-1 + Fn-2

 

Hence, a Fibonacci series can look like this:

F8 = 0 1 1 2 3 5 8 13

or, this:

F8 = 1 1 2 3 5 8 13 21

For illustration purpose, Fibonacci of F8 is displayed as :

 

Fibonacci Animation

 

1. Fibonacci Iterative Algorithm

First we try to draft the iterative algorithm for Fibonacci series.

 

Procedure Fibonacci(n)

   declare f0, f1, fib, loop

  

   set f0 to 0

   set f1 to 1

  

   display f0, f1

  

   for loop ← 1 to n

  

      fib ← f0 + f1  

      f0 ← f1

      f1 ← fib

 

      display fib

   end for

     

end procedure

 

2. Fibonacci Recursive Algorithm

Let us learn how to create a recursive algorithm Fibonacci series. The base criteria of recursion.

 

START

Procedure Fibonacci(n)

   declare f0, f1, fib, loop

  

   set f0 to 0

   set f1 to 1

  

   display f0, f1

  

   for loop ← 1 to n

  

      fib ← f0 + f1  

      f0 ← f1

      f1 ← fib

 

      display fib

   end for

 

END