Problem: Analyze Recursive Depth

Recursive Factorial

public int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Time Complexity

• We make $n$ calls: f(5) -> f(4) -> f(3) -> f(2) -> f(1).
• Total: $\mathbf{O(n)}$.

Space Complexity

• Each call is pushed onto the Recursion Stack.
• There are $n$ frames in the stack at the deepest point.
• Total: $\mathbf{O(n)}$.

Recursive Fibonacci (Unoptimized)

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

Time Complexity

• Each call branches into 2 more calls.
• The depth is $n$.
• Total: $\mathbf{O(2^n)}$. This is exponential and very slow!

Space Complexity

• The stack depth is $n$.
• Total: $\mathbf{O(n)}$. Note that space is $O(n)$, not $O(2^n)$, because frames are popped after each branch completes.