JAVA-205 · Lesson 5 of 12 · 19 min

Recursion and the call stack

▶ Video coming soon A video version of this lesson is on the way.

Merge sort and quicksort both called themselves. On Tuesday, October 12, 2027, Ingrid slows down to look at how that works, because recursion is the tool behind divide and conquer, tree and graph searches and dynamic programming, all still to come this term. Her example is a bike. Tamsin keeps a parts list for each bike model the shop refurbishes, and some entries are themselves assemblies: a wheel is a rim, a hub, 32 spokes and a tube; a drivetrain is a chain, a cassette, a crankset and a derailleur, and the crankset has its own parts. Counting every part in a bike means counting the parts in each assembly, which means counting the parts in its assemblies, and so on. That is a recursive problem.

A method that calls itself

A recursive method solves a problem by calling itself on a smaller version of the same problem. Every recursive method needs two things. A base case is an input small enough to answer directly, without another call. A recursive case reduces the problem to one or more smaller problems, calls the method on them, and combines their answers. Each recursive call must move closer to a base case, or the calls never end.

Java Example · Main.java
public class Main {
    static long factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        for (int n : new int[] {1, 5, 10, 20}) {
            System.out.println(n + "! = " + factorial(n));
        }
    }
}
Output
1! = 1
5! = 120
10! = 3628800
20! = 2432902008176640000

What this code does

factorial(n) is n times factorial(n - 1), and the base case says that the factorial of 1 or less is 1. Each call works on a number one smaller, so the calls always reach the base case. The results use long because 20 factorial is far larger than an int can hold.

Factorial is the classic first example, but it is also one that a plain loop handles just as well. Recursion earns its place when the data itself is recursive, like Tamsin's assemblies, or when the problem splits naturally into smaller copies of itself, like sorting halves.

The call stack

Every method call in Java gets a stack frame: a block of memory that holds its parameters, its local variables and the place to return to when it finishes. The frames are kept on the call stack. When a method calls another, a new frame is pushed on top; when a method returns, its frame is popped and the caller continues from where it left off. A recursive call is no different: factorial(5) pushes a frame for factorial(4), which pushes one for factorial(3), and so on down to factorial(1). Then the frames are popped one by one as each call multiplies and returns.

Java Example · Main.java
public class Main {
    static long factorial(int n, String indent) {
        System.out.println(indent + "call factorial(" + n + ")");
        if (n <= 1) {
            System.out.println(indent + "base case, return 1");
            return 1;
        }
        long result = n * factorial(n - 1, indent + "  ");
        System.out.println(indent + "return " + result);
        return result;
    }

    public static void main(String[] args) {
        factorial(4, "");
    }
}
Output
call factorial(4)
  call factorial(3)
    call factorial(2)
      call factorial(1)
      base case, return 1
    return 2
  return 6
return 24

What this code does

The indent grows by two spaces for each deeper call, so the printout shows the frames stacking up from factorial(4) down to the base case. The returns then come back in the opposite order, each frame multiplying by its own n. Every call that started must finish before its caller can.

Four stacked frames drawn as boxes, factorial(1) at the top and factorial(4) at the bottom above main. Each box shows its value of n and the expression waiting to be completed, such as 4 times question mark. Arrows going up are labeled call; arrows coming down on the right are labeled return 1, return 2, return 6, return 24.
The call stack for factorial(4): frames pile up until the base case, then unwind

When the stack runs out

The call stack has a fixed size, typically a few hundred kilobytes to a megabyte per thread, which is room for several thousand frames of a small method. A recursion that is too deep, or that never reaches its base case, keeps pushing frames until the stack is full, and the JVM throws a StackOverflowError. It is an Error, not an Exception, because it usually means a bug rather than a situation to recover from.

Java Example · Main.java
public class Main {
    static int countParts(int remaining) {
        return 1 + countParts(remaining - 1);
    }

    public static void main(String[] args) {
        System.out.println(countParts(10));
    }
}

What this code does

countParts has no base case, so it calls itself forever with smaller and smaller numbers. Each call pushes a frame until the stack is full and the JVM throws StackOverflowError. The stack trace repeats the same line about a thousand times, which is the quickest way to recognize runaway recursion.

Running it
$ javac Main.java
$ java Main
Exception in thread "main" java.lang.StackOverflowError
	at Main.countParts(Main.java:3)
	at Main.countParts(Main.java:3)
	at Main.countParts(Main.java:3)
	at Main.countParts(Main.java:3)
	at Main.countParts(Main.java:3)
	at Main.countParts(Main.java:3)
	at Main.countParts(Main.java:3)
	... (1017 more lines like these)

The fix is the base case: if (remaining == 0) return 0;. A correct recursion can still overflow if it is simply too deep. Quicksort on sorted input, from lesson 4, recursed 2,000 levels deep and survived, but at 100,000 levels it would not. Java, unlike some languages, does not optimize tail calls (a recursive call that is the very last action of the method), so even a tail-recursive method uses one frame per call. When the depth can grow with n, prefer a loop or an explicit stack.

Recursion on recursive data

Tamsin's parts list is a tree: each assembly has a name, a number of loose parts of its own, and a list of sub-assemblies. Counting every part in an assembly is naturally recursive. The base case is an assembly with no sub-assemblies, whose count is just its own parts. The recursive case adds its own parts to the counts of each sub-assembly. The code mirrors the shape of the data, and no loop over depth levels is needed, however deep the nesting goes.

Java Example · Main.java
import java.util.List;

public class Main {
    record Assembly(String name, int ownParts, List<Assembly> subs) {
        Assembly(String name, int ownParts) { this(name, ownParts, List.of()); }
    }

    static int totalParts(Assembly a) {
        int total = a.ownParts();
        for (Assembly sub : a.subs()) {
            total += totalParts(sub);
        }
        return total;
    }

    static void print(Assembly a, String indent) {
        System.out.println(indent + a.name() + " (" + totalParts(a) + ")");
        for (Assembly sub : a.subs()) print(sub, indent + "  ");
    }

    public static void main(String[] args) {
        Assembly wheel = new Assembly("front wheel", 0, List.of(
                new Assembly("rim", 1), new Assembly("hub", 9), new Assembly("spokes", 32), new Assembly("tube", 1)));
        Assembly crank = new Assembly("crankset", 4, List.of(new Assembly("chainring", 1), new Assembly("crank bolts", 2)));
        Assembly drive = new Assembly("drivetrain", 0, List.of(
                new Assembly("chain", 1), new Assembly("cassette", 1), crank, new Assembly("derailleur", 6)));
        Assembly bike = new Assembly("city bike", 12, List.of(wheel, drive));
        print(bike, "");
    }
}
Output
city bike (70)
  front wheel (43)
    rim (1)
    hub (9)
    spokes (32)
    tube (1)
  drivetrain (15)
    chain (1)
    cassette (1)
    crankset (7)
      chainring (1)
      crank bolts (2)
    derailleur (6)

What this code does

totalParts adds an assembly's own parts to the totals of its sub-assemblies, and an assembly with no sub-assemblies is the base case because its loop does not run. print uses the same pattern to show the tree with one indent per level. The city bike comes to 70 parts, counting the 32 spokes as separate parts.

A small warning about the example: print calls totalParts at every level, so the parts in deep assemblies are counted again for each ancestor. For a bike that does not matter, but it is a first glimpse of the problem that dynamic programming solves in lesson 11: the same work being repeated.

Repeated work: the Fibonacci trap

Some problems split into smaller problems that overlap. The Fibonacci numbers, 1, 1, 2, 3, 5, 8, 13, …, are defined by fib(n) = fib(n − 1) + fib(n − 2). The definition is recursive and translates directly into Java, but each call makes two more calls, and those calls recompute the same values again and again. The number of calls grows roughly like 1.6ⁿ, which is exponential.

Java Example · Main.java
public class Main {
    static long calls = 0;

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

    public static void main(String[] args) {
        for (int n : new int[] {10, 20, 30}) {
            calls = 0;
            long f = fib(n);
            System.out.println("fib(" + n + ") = " + f + " after " + calls + " calls");
        }
    }
}
Output
fib(10) = 55 after 109 calls
fib(20) = 6765 after 13529 calls
fib(30) = 832040 after 1664079 calls

What this code does

The method follows the definition exactly and counts its own calls. fib(20) already takes 13,529 calls, and fib(30) more than 1.6 million, although only 30 different values are ever needed. Lesson 11 fixes this by remembering each answer the first time it is computed.

Thinking recursively

Writing a recursive method well comes down to trusting the recursion. You do not trace every call in your head. Instead you check three things. Is there a base case that answers the smallest inputs directly? Does every recursive call work on a smaller input that moves toward a base case? And, assuming the recursive calls return correct answers for the smaller inputs, does the method combine them into a correct answer for the whole input? If all three hold, the method is correct by the same reasoning as a proof by induction.

Java Example · Main.java
public class Main {
    static String reverse(String s) {
        if (s.length() <= 1) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    static boolean isPalindrome(String s) {
        if (s.length() <= 1) return true;
        if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
        return isPalindrome(s.substring(1, s.length() - 1));
    }

    public static void main(String[] args) {
        System.out.println(reverse("SG-0007-AR"));
        System.out.println(isPalindrome("level"));
        System.out.println(isPalindrome("pedal"));
    }
}
Output
RA-7000-GS
true
false

What this code does

reverse trusts that it can reverse everything after the first character and then puts that first character at the end. isPalindrome compares the outer two characters and, if they match, trusts the recursion to check the middle. Both shrink the string by at least one character per call, so they always reach the base case.

Recursion or iteration?

Choosing between recursion and iteration
Use recursion whenUse a loop when
The data is recursive, such as trees, nested assemblies or foldersThe data is a flat list or a range of numbers
The problem splits into smaller copies of itself, as in merge sortEach step simply moves to the next element
The depth grows like log n or stays smallThe depth could grow with n into the thousands
The recursive version is much clearerSpeed and memory matter more than elegance

Any recursion can be rewritten as a loop with an explicit stack, an ArrayDeque that you push and pop yourself, and lesson 8 does exactly that for depth-first search. The explicit stack lives on the heap, which is much larger than the call stack, so it avoids StackOverflowError for deep inputs.

Try it yourself

Total weight of an assembly

Each Part has a weight in grams and a list of sub-parts. Write the recursive method weight(Part p), which returns the part's own grams plus the weights of all its sub-parts.

The program should print front wheel: 1915 g.

import java.util.List;

public class Main {
    record Part(String name, int grams, List<Part> subs) {
        Part(String name, int grams) { this(name, grams, List.of()); }
    }

    static int weight(Part p) {
        return p.grams();
    }

    public static void main(String[] args) {
        Part hub = new Part("hub", 280, List.of(new Part("axle", 95), new Part("bearings", 40)));
        Part wheel = new Part("front wheel", 0, List.of(new Part("rim", 560), hub, new Part("spokes", 640), new Part("tube", 300)));
        System.out.println(wheel.name() + ": " + weight(wheel) + " g");
    }
}

Try it yourself

Recursive power

Write a recursive power(long base, int exp) that returns base raised to exp, for exp of 0 or more, using power(base, exp) = base × power(base, exp − 1) and power(base, 0) = 1.

The program should print 1, 8, 1024 and 59049, one per line.

public class Main {
    static long power(long base, int exp) {
        return base * exp;
    }

    public static void main(String[] args) {
        System.out.println(power(7, 0));
        System.out.println(power(2, 3));
        System.out.println(power(2, 10));
        System.out.println(power(3, 10));
    }
}

Common mistakes

  • MistakeWriting a recursive method without a base case.

    InsteadAnswer the smallest inputs directly before making any recursive call.

  • MistakeMaking a recursive call on an input that is not smaller.

    InsteadCheck that every call moves toward a base case.

  • MistakeRecursing to a depth that grows with n on large inputs.

    InsteadUse a loop or an explicit ArrayDeque stack; Java does not optimize tail calls.

  • MistakeUsing plain recursion when subproblems overlap, as in Fibonacci.

    InsteadRemember answers you have already computed, as lesson 11 shows.

  • MistakeCatching StackOverflowError to keep going.

    InsteadFix the recursion; the error usually means a bug.

Summary and key terms

  • A recursive method solves a problem by calling itself on smaller inputs; it needs a base case answered directly and a recursive case that moves toward it.
  • Each call gets a stack frame on the call stack holding its parameters and local variables, pushed when the call starts and popped when it returns.
  • Recursion that never reaches a base case, or is simply too deep, fills the stack and causes StackOverflowError, and Java does not optimize tail calls, so very deep recursion should become a loop or use an explicit stack.
  • Recursion fits recursive data such as nested assemblies and trees, and problems that split into smaller copies.
  • When subproblems overlap, as in the naive Fibonacci method, the number of calls can grow exponentially.
  • To write recursion, trust that the recursive calls are correct and check the base case, the progress and the combination.
Recursion
Solving a problem by having a method call itself on smaller inputs.
Base case
An input small enough for a recursive method to answer without calling itself.
Recursive case
The part of a recursive method that reduces the problem and calls itself.
Stack frame
The memory for one method call: its parameters, local variables and return point.
Call stack
The stack of frames for the method calls that have started but not yet returned.
StackOverflowError
The error thrown when the call stack runs out of space.
Tail call
A call that is the very last action of a method; Java does not optimize these away.
Overlapping subproblems
Smaller problems that a recursion solves more than once.
Tree
A recursive structure in which each item can contain further items of the same kind.

Practice problems

Work each problem on paper first, then reveal the answer to check.

  1. What two parts does every correct recursive method have?

    Show answer

    A base case and a recursive case that moves toward it.

  2. What does each recursive call push onto the call stack?

    Show answer

    A new frame with its own parameters and local variables.

  3. Why does a missing base case cause StackOverflowError?

    Show answer

    The calls never stop, so frames pile up until the stack is full.

  4. About how many calls does the naive fib(20) make?

    Show answer

    13,529.

  5. How can you avoid deep recursion on large inputs?

    Show answer

    Use a loop or an explicit stack such as an ArrayDeque.

Lesson quiz · 5 questions

Score 60% or more to complete this lesson.

Take the quiz