Recursion and the call stack

Key points

• Every recursive method needs a base case that returns without recursing, and a step that moves towards it.
• Each call gets its own stack frame with its own parameters and locals. Frames share nothing.
• The frames unwind in reverse: the deepest call returns first, and each caller then finishes its own line.
• No reachable base case means StackOverflowError — an Error, so do not plan to catch it.
• Java does not eliminate tail calls, so depth costs real memory. Rewrite as a loop when the depth is unbounded.
• Naive recursion repeats work: plain Fibonacci recomputes the same values thousands of times.

Example

public class Main {

    static long factorial(int n) {
        if (n <= 1) return 1;            // base case
        return n * factorial(n - 1);     // recursive case
    }

    static int calls = 0;

    static int fibNaive(int n) {
        calls++;
        return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);
    }

    // Carries the answer forward instead of rebuilding it on the way out.
    static long fibFast(int n, long a, long b) {
        return n == 0 ? a : fibFast(n - 1, b, a + b);
    }

    static int depth(int n) {
        return n == 0 ? 0 : 1 + depth(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("factorial(5) = " + factorial(5));
        System.out.println("fibNaive(25) = " + fibNaive(25) + " after " + calls + " calls");
        System.out.println("fibFast(90)  = " + fibFast(90, 0, 1) + " after 90 calls");

        System.out.println("depth(5000)  = " + depth(5000) + " frames pushed and popped");

        try {
            depth(Integer.MAX_VALUE);
        } catch (StackOverflowError e) {
            System.out.println("a base case you never reach -> StackOverflowError");
        }
        System.out.println("every call is a real frame: Java never eliminates a tail call");
    }
}

One base case, one smaller step, and a stack that always has to unwind.