Fibonacci Series Using Recursion

Fibonacci series generates the subsequent number by adding two previous numbers. Fibonacci series starts from two numbers F₀ & F₁. The initial values of F₀ & F₁ 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 −

F₈ = 0 1 1 2 3 5 8 13

or, this −

F₈ = 1 1 2 3 5 8 13 21

For illustration purpose, Fibonacci of F₈ is displayed as −

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<b>display f0, f1</b>for loop ← 1 to n
   
      fib ← f0 &plus; f1   
      f0 ← f1
      f1 ← fib

      <b>display fib</b>
   end for
	
end procedure

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 &plus; f1   
      f0 ← f1
      f1 ← fib

      display fib
   end for

END

Example

Following are the implementations of the above approach in various programming languages −

C C++Java Python

#include <stdio.h>intfibbonacci(int n){if(n ==0){return0;}elseif(n ==1){return1;}else{return(fibbonacci(n-1)+fibbonacci(n-2));}}intmain(){int n =5;printf("Number is: %d", n);printf("\nFibonacci series upto number %d are: ", n);for(int i =0;i<n;i++){printf("%d ",fibbonacci(i));}}

Output

Number is: 5
Fibonacci series upto number 5 are: 0 1 1 2 3

Fibonacci Series Using Recursion