The Call Stack and Recursion

How the Call Stack Works

Every Java program starts execution with a main thread, whose stack begins with a frame for main(). Each method invocation pushes a new frame; each return pops that frame. The stack grows and shrinks continuously as the program runs.

Consider this simple program:

public class CallStackDemo {
    public static void main(String[] args) {
        int x = 3;
        int y = methodA(x);
        System.out.println(y);
    }

    static int methodA(int a) {
        int b = methodB(a * 2);
        return b + 1;
    }

    static int methodB(int p) {
        return p + 10;
    }
}

Frame snapshots during execution:

1. After main starts: one frame — main with args, x = 3, y uninitialised.
2. Calling methodA(3): methodA’s frame is pushed. It holds a = 3 (the parameter receives a copy of x), and b uninitialised. main’s frame waits underneath.
3. Calling methodB(6): methodB’s frame is pushed. It holds p = 6. main and methodA wait underneath.
4. methodB returns 16: its frame is popped. Execution resumes in methodA, which assigns b = 16.
5. methodA returns 17: its frame is popped. Execution resumes in main, which assigns y = 17.
6. main prints and returns: its frame is popped. The thread’s stack is now empty.

Recursion and the Stack

A recursive method calls itself. Each call pushes a new frame with its own copies of parameters and local variables.

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

Calling factorial(5) pushes 5 frames: n=5, n=4, n=3, n=2, n=1. Each frame has its own n. When n=1 hits the base case, the frames unwind — factorial(1) returns 1, factorial(2) returns 2, and so on back up to the original call.

Every frame on the stack occupies real memory (a few hundred bytes typically). If the recursion goes deep enough, the stack runs out of space:

factorial(100_000);  // StackOverflowError

Even though the heap might have gigabytes free, the stack is small (typically 1 MB by default). This is why deep recursion fails while the equivalent loop succeeds:

static int factorialIterative(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

factorialIterative(100_000) uses a single stack frame regardless of input size — it just loops, updating local variables in place.

Tail Recursion

A recursive call is in tail position if it is the very last operation in the method — nothing remains to be done after the call returns. Tail recursion can be rewritten to use an accumulator:

// Standard recursive — NOT tail-recursive (the multiplication happens after the call returns)
static int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

// Tail-recursive version — the recursive call is the last thing
static int factorialTail(int n, int acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, acc * n);
}

In factorialTail, after the recursive call returns, there is nothing left to compute — the returned value is immediately returned to the next frame up.

THE CRITICAL TRAP: Java Does NOT Guarantee Tail-Call Optimisation

In languages like OCaml and Scheme, tail calls are optimised by the compiler: the current frame is replaced by the callee’s frame, so tail recursion consumes constant stack space regardless of depth. This is called tail-call elimination (TCE) or tail-call optimisation (TCO).

Java does not mandate TCO. The JVM specification does not require it, and the standard HotSpot JVM does not implement it for Java code. This means:

// This WILL overflow for large n, even though it is tail-recursive
factorialTail(10_000, 1);  // StackOverflowError

Rewriting a recursive method to be tail-recursive in Java does not prevent StackOverflowError. It is a useful exercise for understanding the shape of recursion, but it does not change the runtime behaviour regarding stack consumption.

If a Tripos question asks you to “make this recursive method tail-recursive”, do so — but be prepared to note that this does not solve the stack overflow problem in Java.

Recursion vs Iteration: Choosing

Factor	Recursion	Iteration
Stack frames per call	One new frame	One frame reused
Overflow risk	Yes, for deep input	No
Code clarity	Excellent for tree/graph traversal, divide-and-conquer	Excellent for simple loops
Space complexity	O(depth) on the stack	O(1) for local variables

Use recursion when the natural structure of the problem is recursive (tree traversal, backtracking) and the depth is bounded. Use iteration when the recursion would be deep and unbounded, or when a simple loop suffices.