Lesson 12.3 · Recursion

Recursion Trees and Cost

Draw the calls as a tree: the number of nodes times the work per node is the time; the tree's height is the stack space.

14 min

Think of it like this

A phone tree where each person calls two more people: after 30 levels, more than a billion calls have been made. Branching recursion grows the same way unless the calls share work.

1.One call vs two calls

factorial makes one call per level: n nodes in a line, O(n) time. Naive Fibonacci makes two calls per level: about 2ⁿ nodes, O(2ⁿ) time, even though there are only n distinct inputs. The same subproblems are solved again and again.

Remembering results (memoisation) collapses the tree back to n distinct nodes: O(n). That idea is the start of dynamic programming.

FibCalls.java

public class Main {
    static long calls = 0;
    static long fib(int n) {
        calls++;
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }
    static long[] memo = new long[100];
    static long memoCalls = 0;
    static long fibMemo(int n) {
        memoCalls++;
        if (n < 2) return n;
        if (memo[n] != 0) return memo[n];
        return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    }
    public static void main(String[] args) {
        System.out.println("fib(30) = " + fib(30) + " with " + calls + " calls");
        System.out.println("fib(30) = " + fibMemo(30) + " with " + memoCalls + " calls (memoised)");
    }
}

Output

fib(30) = 832040 with 2692537 calls
fib(30) = 832040 with 59 calls (memoised)

Quick check

What is the time complexity of a function that makes two recursive calls on n / 2 and does O(1) other work?

Remember

Time ≈ number of calls × work per call.
Branching recursion with overlapping subproblems explodes; memoise it.
Space = maximum depth.

Common mistakes

Calling naive recursive Fibonacci O(n).
Forgetting that substring or array copies inside each call add to the cost.

Command Palette

Recursion Trees and Cost

1.One call vs two calls