Recursion and the call stack

factorial(4) is 4 × factorial(3), and so on down to factorial(0), which is 1: five calls, each waiting for the next. A recursiverecursion: A method that calls itself on a smaller version of its problem, until it reaches a case it answers directly, the base case. Each call waits in its own frame until the call it made returns. method calls itself on a smaller piece of its job, until the piece is small enough to answer directly, the base casebase case: The input a recursive method answers directly, without calling itself, such as factorial(0) = 1. Every other call must move closer to it, or the calls never end and the stack overflows.. Every call gets its own frame on the thread’s stack, holding its parameters and local variables, and the frame stays there until that call returns. The stack has a fixed size, so a recursion that goes too deep, or never reaches its base case, fills it, and the JVM throws StackOverflowError.

You will step through the frames of a small recursion, measure how many frames fit on a thread’s stack, and use the three tools that make recursion practical: memoisation, halving the problem, and turning deep recursion into a loop. Java gives every call a frame, even a call in tail position, so the safe rule is: recursion when the depth stays small, a loop when it grows with the input.

A recursive call waits in its own frame for a smaller call

Every recursive method needs two things: a base case that returns without calling itself, and a recursive case that calls itself on a problem that is strictly closer to the base case. The program below prints each call on the way in and each result on the way out, indented by its depth:

// factorial(n) = n * factorial(n - 1), and factorial(0) = 1 ends the chain.
// The depth parameter only indents the trace, one step per frame on the stack.
long factorial(int n, int depth) {
    String indent = "  ".repeat(depth);
    IO.println(indent + "call factorial(" + n + ")");
    if (n == 0) {
        IO.println(indent + "base case: return 1");
        return 1;
    }
    long result = n * factorial(n - 1, depth + 1);
    IO.println(indent + "return " + n + " * " + (result / n) + " = " + result);
    return result;
}

void main() {
    IO.println("factorial(4) = " + factorial(4, 0));
}

call factorial(4)
  call factorial(3)
    call factorial(2)
      call factorial(1)
        call factorial(0)
        base case: return 1
      return 1 * 1 = 1
    return 2 * 1 = 2
  return 3 * 2 = 6
return 4 * 6 = 24
factorial(4) = 24

Step through the same run frame by frame. Each call pushes a frameframe: The room a method call gets on its thread's stack: its parameters, its local variables and its own operand stack. The JVM creates it when the call starts and removes it when the call returns. onto the call stackcall stack: The frames of a thread's calls that have started and not yet returned, the most recent on top. Its size is fixed when the thread starts; a call that needs more room than is left throws StackOverflowError., and each return removes one:

The trace is the call stack drawn sideways. factorial(4) cannot finish until factorial(3) returns, which waits for factorial(2), and so on: five frames are on the stack at the deepest point, each with its own n. The base case returns first, and the multiplications happen on the way back out, from the innermost frame to the outermost.

Without a base case, frames pile up until the stack overflows

Remove the base case and nothing stops the chain:

// The base case is missing, so every call makes another one until the stack is full.
long factorial(int n) {
    return n * factorial(n - 1);
}

void main() {
    IO.println(factorial(4));
}

The session runs it twice: the first time head keeps the first four lines of what it printed, and the second time grep -c counts the lines of the trace that name the method. After each $ comes the command:

from session import run

# head keeps the first four lines of the error; grep -c counts the lines of the whole trace that name factorial.
run("""
java NoBase.java 2>&1 | head -n 4
java NoBase.java 2>&1 | grep -c "at NoBase.factorial"
""")

# openjdk version "25.0.4.1" LTS
$ java NoBase.java 2>&1 | head -n 4
Exception in thread "main" java.lang.StackOverflowError
	at NoBase.factorial(NoBase.java:3)
	at NoBase.factorial(NoBase.java:3)
	at NoBase.factorial(NoBase.java:3)
$ java NoBase.java 2>&1 | grep -c "at NoBase.factorial"
1019

Each call makes another one and none ever returns, so the frames keep coming, as the dashed path of the diagram shows, until the JVM throws StackOverflowError. Its stack tracestack trace: What an uncaught exception prints: its class and message, then the calls that were open when it was thrown, the most recent first, each with its file and line, and any Caused by sections. More in “IDEs, compiler errors and your first debug” shows the same frame, NoBase.factorial at line 3, over and over: 1,019 times, as the second command counted. The stack held many more frames than that, as the next section measures, but the Throwable documentation allows a JVM to leave frames out of a trace, and this one keeps only the newest. When you see one line repeated like that, look for a base case that is missing or never reached.

The result has its own limit. A long holds at most 9,223,372,036,854,775,807, so factorial(20), about 2.4 × 10¹⁸, is the largest factorial that fits; factorial(21) overflows silently, an integer overflowinteger overflow: What happens when the result of +, -, * or ++ does not fit its integer type: Java keeps the lowest 32 or 64 bits of the true result, so the value wraps round without an error, and Integer.MAX_VALUE + 1 is Integer.MIN_VALUE. More in “Integer arithmetic, division and overflow”. For bigger values, java.math.BigInteger computes exactly.

The stack’s size limits the depth, and the JIT changes it

The Java Virtual Machine Specification gives each thread its own stack, created with the thread, and requires a StackOverflowError when a computation needs a larger stack than is permitted. How many frames fit depends on the stack’s size and on the size of each frame. This program counts:

// How many nested calls fit on the main thread's stack before StackOverflowError?
int depth = 0;

void dive() {
    depth++;
    dive();
}

void main() {
    try {
        dive();
    } catch (StackOverflowError e) {
        // Caught here only to count the frames. Real code should never try to carry on after this error.
    }
    IO.println("main thread: " + "%,d".formatted(depth) + " frames");
}

// The same dive on a thread created with a 64 MiB stack instead of the default.
int depth = 0;

void dive() {
    depth++;
    dive();
}

void main() throws InterruptedException {
    Thread big = Thread.ofPlatform().stackSize(64L << 20).start(() -> {
        try {
            dive();
        } catch (StackOverflowError e) {
            // counting only
        }
    });
    big.join();
    IO.println("64 MiB thread: " + "%,d".formatted(depth) + " frames");
}

StackDepth.java catches the error only to count the frames, and BigStack.java starts a thread only to give it a bigger stack; exceptions and threads have modules of their own later in this track. The session runs them three ways:

from session import run

# -Xint runs every method in the interpreter, whose frames always have the same size, so the counts repeat exactly.
run("""
java -Xint StackDepth.java
java -Xint -Xss8m StackDepth.java
java -Xint BigStack.java
""")

# openjdk version "25.0.4.1" LTS
$ java -Xint StackDepth.java
main thread: 17,640 frames
$ java -Xint -Xss8m StackDepth.java
main thread: 73,814 frames
$ java -Xint BigStack.java
64 MiB thread: 598,108 frames

These runs use -Xint, which makes the JVM interpret every method instead of compiling the busy ones, so each frame of dive() has the same size and the counts repeat exactly. The main thread’s stack is 2 MiB by default on macOS on Apple silicon, as the java command’s documentation lists, -Xss8m sets an 8 MiB stack, and a thread built with Thread.ofPlatform().stackSize(64L << 20) gets 64 MiB. Dividing each size by its count gives the room a frame takes:

The step from 2 MiB to 8 MiB added 56,174 frames for 6 MiB, 112 bytes each. The rest of each stack, about 120,000 bytes in all three runs (2 MiB less 17,640 frames of 112 bytes), holds something other than the frames of dive(), which is why the share per frame is highest in the smallest stack. A method with more parameters and local variables has bigger frames, and fits fewer. With the just-in-time compilerJIT compilation: Just-in-time compilation: while a program runs, the JVM compiles the methods that run often from bytecode to native machine code, so a Java program gets faster after a short warm-up. The option -Xint switches it off. More in “What Java is, how it runs and where it is used” on, which is how Java normally runs, the same program gives a different count each time:

from session import run

# With the JIT compiler on (the default), the count changes from one run to the next.
run("""
java StackDepth.java
java StackDepth.java
java StackDepth.java
""")

# openjdk version "25.0.4.1" LTS
$ java StackDepth.java
main thread: 36,140 frames
$ java StackDepth.java
main thread: 40,352 frames
$ java StackDepth.java
main thread: 36,072 frames

The JIT compiles dive() while the dive is under way, and from then on each frame is smaller, so the count depends on when compilation finished. The documentation of stackSize warns that its effect is “highly platform dependent”, and the JVM may treat it as a suggestion. So never write code that needs a particular depth to work: if the input decides how deep a recursion goes, a big enough input will overflow some stack somewhere.

Tail calls still use the stack

A call is in tail position when it is the last thing a method does, as in return sumTo(n - 1, total + n);. Some languages reuse the caller’s frame for such a tail calltail call: A call that is the last thing a method does, its result returned as it is, as in return sumTo(n - 1, total + n);. HotSpot still gives it a frame of its own, so tail recursion can overflow the stack.. HotSpot, the JVM in this JDK, does not:

// The recursive call is the last thing sumTo does (a tail call), yet each call still needs a frame of its own.
long sumTo(long n, long total) {
    if (n == 0) {
        return total;
    }
    return sumTo(n - 1, total + n);
}

// The same computation as a loop: one frame, whatever n is.
long sumToLoop(long n) {
    long total = 0;
    while (n > 0) {
        total += n;
        n--;
    }
    return total;
}

void main() {
    IO.println("sumTo(3, 0) = " + sumTo(3, 0));
    IO.println("sumToLoop(3) = " + sumToLoop(3));
    IO.println("sumTo(1000, 0) = " + sumTo(1000, 0));
    IO.println("sumToLoop(1000000) = " + sumToLoop(1_000_000));
    try {
        IO.println("sumTo(1000000, 0) = " + sumTo(1_000_000, 0));
    } catch (StackOverflowError e) {
        IO.println("sumTo(1000000, 0): StackOverflowError");
    }
}

sumTo(3, 0) = 6
sumToLoop(3) = 6
sumTo(1000, 0) = 500500
sumToLoop(1000000) = 500000500000
sumTo(1000000, 0): StackOverflowError

Step through sumTo(3, 0) beside the loop that computes the same total:

Three nested calls, or a thousand, are fine, but a million need a million frames, and the stack overflows although no frame has any work left to do after its call. The loop computes the same total in one frame. A tail-recursive method turns into a loop almost mechanically: the parameters become variables, and the recursive call becomes an update of those variables followed by another pass.

Memoisation computes each smaller problem once

Some recursions solve the same small problem many times. The Fibonacci numbers are the classic case: fib(n) calls fib(n - 1) and fib(n - 2), and fib(n - 1) calls fib(n - 2) again.

long calls = 0;

// Plain recursion: fib(n - 1) and fib(n - 2) solve the same smaller problems again and again.
long fib(int n) {
    calls++;
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

// Memoised: each answer is worked out once and kept in memo[n]; 0 means "not known yet".
long[] memo = new long[93];

long fibMemo(int n) {
    calls++;
    if (n < 2) {
        return n;
    }
    if (memo[n] != 0) {
        return memo[n];
    }
    memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
    return memo[n];
}

void main() {
    for (int n : new int[] {5, 10, 20, 30, 40}) {
        calls = 0;
        long value = fib(n);
        IO.println("fib(" + n + ") = " + value + " after " + "%,d".formatted(calls) + " calls");
    }
    for (int n : new int[] {5, 40, 90}) {
        calls = 0;
        memo = new long[93];
        long value = fibMemo(n);
        IO.println("fibMemo(" + n + ") = " + value + " after " + calls + " calls");
    }
}

fib(5) = 5 after 15 calls
fib(10) = 55 after 177 calls
fib(20) = 6765 after 21,891 calls
fib(30) = 832040 after 2,692,537 calls
fib(40) = 102334155 after 331,160,281 calls
fibMemo(5) = 5 after 9 calls
fibMemo(40) = 102334155 after 79 calls
fibMemo(90) = 2880067194370816120 after 179 calls

The plain version made 15 calls for fib(5) and 331,160,281 for fib(40), and the count grows by a factor of about 1.6 with each step of n, the same rate as the Fibonacci numbers themselves. Its depth, though, is only 40: the problem is the number of calls, not the stack. Memoisationmemoisation: Keeping each answer of a function once it is worked out, in an array or a map, so that a later call with the same argument returns it at once instead of working it out again. keeps each answer once it is known, here in an array, so every value from 2 to n is worked out only once. Step through fibMemo(5) and watch the array fill:

fibMemo(5) made 9 calls where fib(5) made 15, and for any n of 1 or more the memoised version makes 2n − 1: 79 calls for fib(40) and 179 for fib(90). It cuts the calls, not the depth: the first calls still go down one level at a time, so fibMemo(40) is 40 frames deep at its deepest. A HashMap does the same job when the arguments are not small numbers. The array has 93 places because fib(92) is the largest Fibonacci number that fits in a long.

Halving the problem keeps the depth tiny

A recursion is safe when each call makes the problem much smaller, not just one step smaller. Raising a number to a power shows the difference:

int calls = 0;

// base^exp the slow way: one call, and one multiplication, for each unit of exp.
long powerSlow(long base, int exp) {
    calls++;
    if (exp == 0) {
        return 1;
    }
    return base * powerSlow(base, exp - 1);
}

// Halving: base^exp = (base^(exp / 2))^2, times one more base when exp is odd.
long power(long base, int exp) {
    calls++;
    if (exp == 0) {
        return 1;
    }
    long half = power(base, exp / 2);
    long square = half * half;
    return exp % 2 == 0 ? square : square * base;
}

void main() {
    calls = 0;
    IO.println("powerSlow(3, 39)     = " + powerSlow(3, 39) + " after " + calls + " calls");
    calls = 0;
    IO.println("power(3, 39)         = " + power(3, 39) + " after " + calls + " calls");
    calls = 0;
    IO.println("power(1, 1000000000) = " + power(1, 1_000_000_000) + " after " + calls + " calls");
    calls = 0;
    IO.println("power(2, 62)         = " + power(2, 62) + " after " + calls + " calls");
    calls = 0;
    IO.println("power(2, 64)         = " + power(2, 64) + " after " + calls + " calls");
}

powerSlow(3, 39)     = 4052555153018976267 after 40 calls
power(3, 39)         = 4052555153018976267 after 7 calls
power(1, 1000000000) = 1 after 31 calls
power(2, 62)         = 4611686018427387904 after 7 calls
power(2, 64)         = 0 after 8 calls

Step through power(3, 39): down through the halved exponents, then back up through the squares:

powerSlow makes one call per unit of the exponent, 40 calls for 3³⁹, and an exponent of a billion would overflow the stack. power uses base^exp = (base^(exp / 2))², times one more base when the exponent is odd, so each call halves the exponent: 7 calls for 3³⁹, and only 31 for an exponent of a billion, as the third line shows. The depth grows with the number of binary digits of the exponent, which keeps it tiny. The last line is a reminder that recursion does not protect you from overflow: 2⁶⁴ does not fit in a long, and the result wraps to 0. Computing powers modulo a number, as the exercise below does, keeps every intermediate value small.

When the depth grows with the input, use a loop

When the depth of a recursion grows with the size of the input (one call per character, per list element or per unit of a count), rewrite it as a loop before a large input reaches it:

• Tail recursion: replace the call with a loop that updates the parameters, as sumToLoop does.
• A running count or total: keep the state in local variables, and visit the input once with for or while.
• Branching recursion over trees or grids: keep your own stack of work still to do (an ArrayDeque, from the collections module) and loop until it is empty, so the size of the input lives on the heap instead of the thread’s stack.

Raising the stack size with -Xss or a thread with a larger stack only moves the limit, and catching StackOverflowError is not a fix: the error can strike in the middle of any method on the stack and leave its work half done. Answer the questions below for a recursion of your own:

In short: recursion stays the clearer choice when the depth is bounded by something small, such as the height of a balanced tree or the number of binary digits of an exponent; memoise when the same smaller problems come back; and write a loop, with a stack of your own where the problem branches, when the depth grows with the input.

Practise: modular power and bracket depth

RecursionCheck.java has two methods that work on small inputs and overflow the stack on large ones, so three of its eleven checks fail and the program ends with exit status 1:

// Try it yourself: rewrite both methods so that every check passes, then run java RecursionCheck.java.
//
// power(base, exp, mod) is base to the power exp, modulo mod, for base >= 0, exp >= 0 and 1 <= mod <= 2,000,000,000
// (so that the product of two remainders still fits in a long). maxDepth(parens) is the deepest nesting of a balanced
// string of '(' and ')': 0 for "", 1 for "()()", 3 for "((()))".
long power(long base, int exp, long mod) {
    if (exp == 0) {
        return 1 % mod;
    }
    return base % mod * power(base, exp - 1, mod) % mod; // one call for each unit of exp
}

int maxDepth(String parens) {
    return deepest(parens, 0, 0);
}

// The deepest level from position i on, when the level before position i is depth: one call per character.
int deepest(String s, int i, int depth) {
    if (i == s.length()) {
        return 0;
    }
    int here = s.charAt(i) == '(' ? depth + 1 : depth - 1;
    return Math.max(here, deepest(s, i + 1, here));
}

int passed = 0;
int total = 0;

void report(String call, String got, String expected) {
    total++;
    if (got.equals(expected)) {
        passed++;
        IO.println("PASS  " + call + " is " + got);
    } else {
        IO.println("FAIL  " + call + " is " + got + ", expected " + expected);
    }
}

void checkPower(long base, int exp, long mod, long expected) {
    String call = "power(" + base + ", " + exp + ", " + mod + ")";
    try {
        report(call, String.valueOf(power(base, exp, mod)), String.valueOf(expected));
    } catch (StackOverflowError e) {
        report(call, "a StackOverflowError", String.valueOf(expected));
    }
}

void checkDepth(String name, String parens, int expected) {
    String call = "maxDepth(" + name + ")";
    try {
        report(call, String.valueOf(maxDepth(parens)), String.valueOf(expected));
    } catch (StackOverflowError e) {
        report(call, "a StackOverflowError", String.valueOf(expected));
    }
}

void main() {
    checkPower(2, 10, 1000, 24);
    checkPower(3, 0, 7, 1);
    checkPower(5, 3, 1, 0);
    checkPower(10, 18, 1_000_000_007, 49);
    checkPower(7, 1_000_000_000, 1_000_000_007, 312_556_845);
    checkPower(123_456_789, 987_654_321, 1_000_000_007, 652_541_198);
    checkDepth("\"\"", "", 0);
    checkDepth("\"()()\"", "()()", 1);
    checkDepth("\"(())()\"", "(())()", 2);
    checkDepth("\"((()))\"", "((()))", 3);
    checkDepth("a million nested pairs", "(".repeat(1_000_000) + ")".repeat(1_000_000), 1_000_000);
    IO.println(passed + " of " + total + " checks pass");
    if (passed < total) {
        System.exit(1);
    }
}

PASS  power(2, 10, 1000) is 24
PASS  power(3, 0, 7) is 1
PASS  power(5, 3, 1) is 0
PASS  power(10, 18, 1000000007) is 49
FAIL  power(7, 1000000000, 1000000007) is a StackOverflowError, expected 312556845
FAIL  power(123456789, 987654321, 1000000007) is a StackOverflowError, expected 652541198
PASS  maxDepth("") is 0
PASS  maxDepth("()()") is 1
PASS  maxDepth("(())()") is 2
PASS  maxDepth("((()))") is 3
FAIL  maxDepth(a million nested pairs) is a StackOverflowError, expected 1000000
8 of 11 checks pass

1. Copy RecursionCheck.java and rewrite power and maxDepth.
2. Run it with java RecursionCheck.java.
3. You are done when the last line reads “11 of 11 checks pass”.

A first hint: power can stay recursive if each call halves the exponent, as FastPower.java does; take the remainder after every multiplication. maxDepth needs one counter that goes up at ( and down at ), and a loop that remembers the highest value it reached.

Then work through the practice below. It moves from frames to loops, begins with the recursion idea you answer worst, and explains every option as soon as you choose:

Interview questions

Fresher · What is a base case in recursion, and what happens if a recursive method has none?

The base case is the input a recursive method answers directly, without calling itself: factorial(0) returns 1, and a search of an empty range returns “not found”. Every other call must move closer to a base case, by making the problem smaller. Without a base case, or when the calls never reach it, each call starts another, every call adds a frame to the thread’s stack, and none of them returns. The compiler does not detect this; at run time the stack fills up after some tens of thousands of frames on the default stack, and the JVM throws StackOverflowError, whose trace repeats the same method line over and over. Check the smallest inputs, such as 0, 1 and an empty string, first.

The next question is usually about a deeper input or a repeated subproblem. Here is one of each; choose, then see why each option is right or wrong:

Two longer questions of this module build on this lesson: a folder walk that meets an archive nested 50,000 levels deep, and how long a plain recursive fib(50) takes compared with the faster ways to compute it.

Key takeaways

• A recursive method needs a base case that returns directly and that every call is sure to reach, and a recursive case that makes the problem smaller.
• Each call has its own frame on the thread’s stack until it returns, so a missing base case, or a depth that grows with the input, ends in StackOverflowError.
• On this JDK the default 2 MiB stack held 17,640 frames of a trivial method in the interpreter, about 112 bytes each; with the JIT on the count changes from run to run, so never rely on an exact depth.
• Java does not remove tail calls, so tail recursion overflows like any other; rewrite it as a loop whose variables take the parameters’ place.
• Memoisation cut fib(40) from 331,160,281 calls to 79 but not its depth, and halving the problem kept the depth at 31 calls for an exponent of a billion.
• When the depth grows with the input, write a loop, with a stack of your own on the heap where the recursion branches.