# Fibonacci Iterative vs. Recursive

Fibonacci series:

fib(n) = fib(n-1) + fib(n-2) → for n > 1
fib(n) = 1→ for n = 0, 1

Fibonacci can be solved iteratively as well as recursively

## Time Complexity:

Calculating the time complexity of the recursive approach is not so straightforward, so we are going to dive in

`fib(n):    if n <= 1        return 1    return fib(n - 1) + fib(n - 2)`

for n > 1:
T(n) = T(n-1) + T(n-2) + 4 (1 comparison, 2 subtractions, 1 addition)

Let’s say c = 4 and try to first establish a lower bound by approximating that T(n-1) ~ T(n-2) , though T(n-1) ≥ T(n-2), hence lower bound

`T(n) = T(n-1) + T(n-2) + c     = 2T(n-2) + c    //from the approximation T(n-1) ~ T(n-2)     = 2*(2T(n-4) + c) + c     = 4T(n-4) + 3c     = 8T(n-6) + 7c     = 2^k * T(n - 2k) + (2^k - 1)*cLet's find the value of k for which: n - 2k = 0k = n/2T(n) = 2^(n/2) * T(0) + (2^(n/2) - 1)*c     = 2^(n/2) * (1 + c) - ci.e. T(n) ~ 2^(n/2)`

now for the upper bound, we can approximate T(n-2) ~ T(n-1) as T(n-2) ≤ T(n-1)

`T(n) = T(n-1) + T(n-2) + c     = 2T(n-1) + c    //from the approximation T(n-1) ~ T(n-2)     = 2*(2T(n-2) + c) + c     = 4T(n-2) + 3c     = 8T(n-3) + 7c     = 2^k * T(n - k) + (2^k - 1)*cLet's find the value of k for which: n - k = 0k = nT(n) = 2^n * T(0) + (2^n - 1)*c     = 2^n * (1 + c) - ci.e. T(n) ~ 2^n`

Hence the time taken by recursive Fibonacci is O(2^n) or exponential.

## Space Complexity:

For Fibonacci recursive implementation or any recursive algorithm, the space required is proportional to the maximum depth of the recursion tree, because, that is the maximum number of elements that can be present in the implicit function call stack.

Below is a diagrammatic representation of the Fibonacci recursion tree for fib(6):