Fibonacci Series

In this tutorial we will learn to find Fibonacci series using recursion.

Fibonacci Series

Fibonacci series are the numbers in the following sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ....

By definition, the first two numbers are 0 and 1. And each subsequent numbers in the series is equal to the sum of the previous two numbers.

Fibonacci Recursive Function

F(n) = 1                when n <= 1
     = F(n-1) + F(n-2)  when n > 1

i.e.
F(0) = 0

F(1) = 1

F(2) = F(2-1) + F(2-2)
     = F(1) + F(0)
     = 1 + 0
     = 2

Find the 6th element of the Fibonacci series i.e., F(5)

Using the formula given above we can write the following.

F0  F1  F2  F3  F4  F5
0   1   1   2   3   5

So, the 6th element i.e., F(5) = 5

Fibonacci Pseudo Code

Fibo(n)
Begin
  if n <= 1 then
       Return n;
  else
       Return Call Fibo(n-1) + Call Fibo(n-2);
  endif
End

Fibonacci C Code

/*fibonacci series
recursive and non-recursive
*/

#include <stdio.h>

//function declaration
int fibo(int n);
int nonRecFibo(int n);

int main(){
  //variable declaration
  int n, f;
  
  //input
  printf("Enter n: ");
  scanf("%d", &n);
  
  //recursive
  f = fibo(n);
  printf("Recursive Fibo: %d\n", f);
  
  //non-recursive
  f = nonRecFibo(n);
  printf("Non-Recursive Fibo: %d\n", f);
  
  return 0;
}

//function definition
int fibo(int n){
  if(n <= 1)
    return n;
  else
    return fibo(n-1) + fibo(n-2);
}

int nonRecFibo(int n){
  int i, a, b, f;
  if(n <= 1)
    return n;
  else{
    a = 0, b = 1, f = 0;
    for(i = 2; i <= n; i++){
      f = a + b;
      a = b;
      b = f;
    }
  }
  return f;
}