# Fibonacci Using Recursion

Posted By on October 16, 2014

a direct recusrive implementation mathematical recurance relation given.

 `#include` `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).

#### Posted by Akash Kurup

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

Website: http://world4engineers.com