Fibonacci Using Recursion

Posted By on October 16, 2014


Download PDF
Linear Inequalitites and Linear Equations
Tower of Hanoi using Recursion

a direct recusrive implementation mathematical recurance relation given.

#include<stdio.h>
int fib(int n)
{
   if (n <= 1)
      return n;
   return fib(n-1) + fib(n-2);
}
int main ()
{
  int n = 9;
  printf("%d", fib(n));
  getchar();
  return 0;
}

Time Complexity: T(n) = T(n-1) + T(n-2) which is exponential.
We can observe that this implementation does a lot of repeated work (see the following recursion tree). So this is a bad implementation for nth Fibonacci number.

                         fib(5)
                     /
               fib(4)                fib(3)
             /                      /
         fib(3)      fib(2)         fib(2)    fib(1)
        /             /           /
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /
fib(1) fib(0)

Extra Space: O(n) if we consider the fuinction call stack size, otherwise O(1).

Linear Inequalitites and Linear Equations
Tower of Hanoi using Recursion

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com