Analyzing Recursion

The problem

You wrote a tidy recursive Fibonacci function. It returns fib(10) instantly. Feeling good, you ask for fib(45) — and your terminal just sits there. Seconds pass. Your laptop fan spins up. For a function that is four lines long, something has gone badly wrong.

There is no loop in the code, so the usual trick of "count the iterations" gives you nothing to count. How do you put a Big-O on a function whose only visible operation is calling itself?

A first attempt

Here is the function that is hanging:

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

You might guess it is linear — after all, each call looks like it does a constant amount of work. But guessing is not analysis. To really count, you would have to draw the entire tree of calls fib(45) triggers and tally the nodes. Do that by hand and you will fill a page before you reach depth 6. The naive eyeball approach does not scale, so you need a tool that summarizes the whole tree at once.

The insight

Describe the running time recursively, just like the function. Let T(n) be the number of operations fib(n) performs. Reading the code straight off:

T(n) = T(n - 1) + T(n - 2) + O(1)

The base cases cost O(1). That equation is a recurrence relation — the cost of a problem written in terms of the cost of its subproblems. Solve the recurrence and you have the Big-O, no tree-drawing required.

Two shapes cover most recursive code you will meet:

• Linear recursion — one call to a smaller input: T(n) = T(n - 1) + O(1), which unrolls to O(n).
• Branching recursion — two calls: T(n) = T(n - 1) + T(n - 2) + O(1), which grows like O(φⁿ), roughly O(2ⁿ).

Fibonacci is branching, and that exponential is exactly why fib(45) melts your CPU.

How it works

T(n) = T(n-1) + c
     = T(n-2) + c + c
     = T(n-3) + c + c + c
     ...
     = T(0) + n*c   ->  O(n)

The code

The instrumented version below counts its own calls, so you can see the explosion.

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


fib(20)
print(calls)  # 13529 calls for n = 20

let calls = 0;

function fib(n: number): number {
  calls++;
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

fib(20);
console.log(calls); // 13529 calls for n = 20

static long calls = 0;

static int fib(int n) {
    calls++;
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

// fib(20) -> 13529 calls

long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

/* fib(20) -> 13529 calls */

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

// fib(20) -> 13529 calls

Complexity

When to use it

Practice

Recap

• A recurrence relation expresses a function's running time in terms of its subproblems.
• Unroll linear recurrences and count the tree for branching ones; watch for exponential blowups.
• Time counts every node; space counts only the deepest live path.