Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 201 ยท Methods

Recursion

Learn recursion in Java - base cases, how the call stack works, factorial, Fibonacci, power and sums, StackOverflowError, recursion vs loops and memoization.

A recursive method is a method that calls itself. That sounds like a trick that should never end, and if you write it carelessly, it doesn't. Written well, recursion lets you solve a big problem by solving a slightly smaller copy of the same problem, again and again, until the problem is so small the answer is obvious.

Some problems are naturally recursive: folders contain folders, a JSON value contains JSON values, a sorted list splits into two smaller sorted lists. For those, a recursive method is often shorter and clearer than a loop. This lesson shows how recursion works inside the JVM, how to write it safely, where it breaks (StackOverflowError), and how to make slow recursion fast with memoization.

The two parts of every recursive method

Every correct recursive method has two parts:

  1. A base case: an input small enough to answer directly, without another call.
  2. A recursive case: the method calls itself with an input that is closer to the base case, then uses that result.

Here is the classic example, the factorial n! = n ร— (n - 1) ร— ... ร— 1. Notice that 5! = 5 ร— 4!, and 4! = 4 ร— 3!, and so on, until 0! = 1:

Java Factorial, the recursive way

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Two questions check any recursive method:

  • Does every call move toward the base case? Here n - 1 gets smaller each time.
  • Does every path reach a base case? A negative n never hits 0, so factorial(-1) would recurse forever. A careful version rejects it: if (n < 0) throw new IllegalArgumentException(...).

The return type is long because factorials grow fast: 20! is the largest that fits in a long, and 21! silently overflows (see Working with Numbers). For bigger values you'd use BigInteger from BigInteger and BigDecimal.

What actually happens: the call stack

Each time a method is called, the JVM creates a stack frame for it: a small block of memory that holds that call's parameters and local variables, plus where to return to. Frames are stacked on top of each other. When a method returns, its frame is removed and execution continues in the frame below.

With recursion, each call gets its own frame with its own n. The calls don't share variables. You can see the frames pile up and unwind by printing with an indent that grows with the depth:

Java Watching the call stack grow and shrink

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Read the output from top to bottom. The calls go down to sumTo(0), which answers immediately. Then the returns come back up in reverse order: the call for 1 finishes first, the call for 4 finishes last. The work after the recursive call (n + rest) happens on the way back up, which is why the "return" lines appear in reverse order.

This is the mental model to keep: recursion = a stack of paused calls, each waiting for the one above it to answer.

More classic examples

Power by repeated squaring

Computing base^exp by multiplying exp times takes exp steps. Recursion gives a much faster method: x^10 = (x^5)^2 and x^5 = x ร— x^4. Each step halves the exponent, so x^1000 needs about 10 levels of calls, not 1,000.

Sum of digits and string reversal

Recursion also works on strings: handle the first character, then recurse on the rest.

Java Power, digit sum and reversing a string

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

In power, the result of the recursive call is stored in half and used twice. Writing power(base, exp / 2) * power(base, exp / 2) would give the same answer but make two calls at every level, throwing away the whole speed advantage.

The reverse method is a nice illustration, but don't use it for real work: each substring copies the string, so it does far more work than new StringBuilder(s).reverse() (see StringBuilder).

You don't have to copy an array to recurse on part of it. Pass the array plus the range (low, high) you're interested in. Binary search on a sorted array checks the middle element, then searches only the half that can contain the target:

Java Recursive binary search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

This method has two base cases, which is common. The range shrinks by half each call, so even an array of a billion elements needs only about 30 levels. A helper signature like this, with extra parameters for the range, is the usual way to recurse over arrays. Often you add a public one-argument method that calls the helper with the starting range.

StackOverflowError: when recursion goes too deep

The call stack has a fixed size (typically 512 KB to 1 MB per thread by default, set with the -Xss JVM option). Each frame uses some of it. If recursion goes too deep, either because the base case is never reached or because the input is simply huge, the JVM throws StackOverflowError.

The following example fails on purpose. The first method has no base case at all; the second has a correct base case but is asked to go a million levels deep:

Java Two ways to overflow the stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The exact count depends on the JVM, the stack size and how big each frame is, so it varies from run to run and machine to machine. On our server it's somewhere above 100,000 levels for these tiny methods; methods with more parameters and locals overflow much sooner, and threads with small stacks sooner still. Two lessons follow:

  • A missing or unreachable base case is a bug, and StackOverflowError is its symptom. Read the stack trace: the same method repeated hundreds of times tells you exactly which one.
  • Recursion depth must stay modest. Recursing once per element of a list with a million elements will crash. Recursing once per halving (binary search, power) or once per level of a tree is fine.

Catching StackOverflowError is shown here only to keep the demo running. It's an Error, not an Exception, and in real code you fix the recursion instead of catching it. Java also does not do tail-call optimization: even a call in "tail position" like return countDown(n - 1) still uses a new frame, unlike in some functional languages.

Recursion vs loops

Anything you can write recursively, you can write with a loop (and sometimes an explicit stack), and vice versa. Which one should you choose?

Use a loop when... Use recursion when...
The problem is a straight sequence: sum a list, count to n The data is nested: trees, folders, nested menus, expressions
The depth could be large (one step per element) The depth stays small (logarithmic or tree height)
Performance matters at every call The recursive version is much clearer

Factorial and summing are clearer as loops in real Java code; we use them here because they show the mechanics. Here is the iterative factorial for comparison:

Java
long factorialLoop(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Where recursion shines is branching structure. Printing a nested folder tree, evaluating (2 + 3) * (4 - 1), or generating every arrangement of letters all take a few lines recursively and get messy with loops. You'll see such problems in Graphs, Recursion and Backtracking.

Fibonacci and memoization

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, ..., where each number is the sum of the two before it. The direct recursive translation is beautiful and terribly slow:

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

Each call makes two calls, and they repeat the same work: fib(5) computes fib(3) twice and fib(2) three times. The number of calls grows roughly like 1.6^n, so fib(50) would take billions of calls.

Memoization fixes this: remember each answer the first time you compute it, and look it up next time. A HashMap (or an array, when n is small) does the job:

Java Naive vs memoized Fibonacci

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The naive version needs 2,692,537 calls for fib(30); the memoized version needs 59. Because the memo is kept between calls, memoFib(90) reuses everything up to 30 and needs only 121 more calls. That is the difference between "instant" and "never finishes".

You may be tempted to write memo.computeIfAbsent(n, k -> memoFib(k - 1) + memoFib(k - 2)). Don't: modifying a HashMap from inside its own computeIfAbsent throws ConcurrentModificationException. The explicit get/put above is the safe pattern. (Maps are covered in HashMap.)

When a recursive method calls itself more than once with overlapping inputs, think memoization. When it calls itself once per step, think "would a loop be simpler?". When it splits the input in half, recursion is usually perfect as it is.

Writing a recursive method: a checklist

  1. Define the method in words. "digitSum(n) returns the sum of the digits of n." Trust that definition when you make the recursive call.
  2. Find the smallest inputs and answer them directly. Those are your base cases. Check them first in the method.
  3. Express the answer for n using a smaller input. digitSum(n) = last digit + digitSum(n without the last digit).
  4. Make sure every call shrinks the input, and that bad inputs (negatives, null) are rejected rather than recursing forever.
  5. Estimate the depth. If it can reach many thousands, use a loop instead.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does f(4) return? int f(int n) { if (n == 1) return 1; return n + f(n - 1); }

    f(4) = 4 + f(3) = 4 + 3 + f(2) = 4 + 3 + 2 + f(1) = 4 + 3 + 2 + 1 = 10.
  2. 2. What happens when you call the method above with f(0)?

    The only base case is n == 1. Starting from 0, n only gets smaller and never reaches 1, so the stack fills up until the JVM throws StackOverflowError.
  3. 3. In what order do the lines print when show(3) runs? void show(int n) { if (n == 0) return; show(n - 1); IO.println(n); }

    Each call recurses before printing, so printing happens on the way back up. show(1) finishes first and prints 1, then show(2) prints 2, then show(3) prints 3.
  4. 4. Why is the naive recursive Fibonacci method so slow?

    fib(n) calls fib(n - 1) and fib(n - 2), which overlap heavily, so the number of calls grows exponentially. Memoization stores each answer once.
  5. 5. Which recursive method is safe for very large inputs, such as n = 1,000,000,000?

    Halving n reaches the base case in about 30 calls. The others need hundreds of millions of stack frames and would overflow the stack.

Summary

  • A recursive method calls itself; it needs a base case answered directly and a recursive case that moves toward it.
  • Every call gets its own stack frame with its own parameters and locals; frames unwind in reverse order.
  • Too-deep recursion, from a missing base case or a huge input, throws StackOverflowError. Java has no tail-call optimization.
  • Halving recursion (binary search, fast power) stays shallow; one-call-per-element recursion does not.
  • Prefer loops for simple sequences and recursion for nested or branching structures.
  • Memoization caches results so overlapping recursive calls are computed once, turning exponential work into linear work.

Next: Variable Arguments (Varargs), where you'll write methods that accept any number of arguments.