# Recursion Trees and Exponential Recursion — Time & Space Complexity (Big-O)

Source: https://www.skillbyai.com/en/big-o/r-tree

> Use recursion trees to analyse recursive algorithms, including naive Fibonacci.

## Drawing the calls

A **recursion tree** draws each call as a node, labelled with the work done in that call outside its recursive calls. The total running time is the **sum over all nodes**. For merge sort, the root does n work, the two children do n/2 each (n total), the four grandchildren n/4 each (n total), and so on for log₂ n levels: **n per level × log n levels = O(n log n)**. For **naive Fibonacci**, `fib(n)` calls `fib(n-1)` and `fib(n-2)`; the tree branches twice at almost every node, so the number of calls grows exponentially. It is bounded above by O(2ⁿ), and more precisely grows like φⁿ, where φ ≈ 1.618 is the golden ratio. Even fib(50) needs tens of billions of calls. The same subproblems are computed again and again, which is exactly what **memoisation** and **dynamic programming** fix: storing each fib(k) once makes the algorithm **O(n)** time. Recursion trees make such repeated work visible.

## Naive and memoised Fibonacci

The memoised version computes each value once.

```python
def fib_naive(n):
    if n < 2:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
# T(n) = T(n-1) + T(n-2) + O(1)  ->  exponential, about 1.618^n calls

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
# each of fib(0..n) computed once -> O(n) time, O(n) space for cache and call stack

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
# O(n) time, O(1) extra space
```

## A family tree of phone calls

Naive Fibonacci is like a rumour where every person phones two others, who each phone two more: the number of calls explodes, and most people hear the same news many times. Memoisation is a notice board where each piece of news is posted once.

**Quiz:** Why is naive recursive Fibonacci exponential?

- [ ] It uses a loop inside the recursion
- [x] It recomputes the same subproblems many times, with the call tree branching twice at each level
- [ ] Python recursion is slow
- [ ] It stores every result in memory

*Answer:* It recomputes the same subproblems many times, with the call tree branching twice at each level. Overlapping subproblems are recomputed, so the number of calls grows exponentially.