Programming

Tracing recursive Java methods

Recursion is one of the most important ideas in programming. Once you know how to trace a recursive method by hand — following each call down to the base case and then unwinding back up — you can read, write, and debug recursive code with confidence.

Core idea

A recursive method calls itself with a smaller or simpler input. It must have a base case that stops the recursion, and every recursive call must move toward that base case to avoid infinite recursion.

Go to full practice page Back to Programming tag

Two kinds of recursion

Linear recursion means the method makes exactly one recursive call per execution. The call chain is a straight line from the original call down to the base case, and then it unwinds one frame at a time. Examples include computing a factorial, summing integers from 1 to n, and raising a number to a power.

Branching recursion means the method makes two or more recursive calls per execution. This creates a call tree instead of a line. Examples include computing Fibonacci numbers, counting paths through a grid, and tribonacci sequences. The total work can grow exponentially with small inputs.

How the call stack works

Each time a method is called, Java pushes a new stack frame onto the call stack. That frame holds the local variables and the return address for that call. When the method returns, its frame is popped off.

Recursive methods push many frames in a row. The base case is the deepest frame. Once it returns, each waiting frame can finish and return too — this is called unwinding.

Call stack diagram for factorial(4)

factorial(4) waits for factorial(3)
  factorial(3) waits for factorial(2)
    factorial(2) waits for factorial(1)
      factorial(1) waits for factorial(0)
        factorial(0) returns 1   ← base case
      factorial(1) returns 1 × 1 = 1
    factorial(2) returns 2 × 1 = 2
  factorial(3) returns 3 × 2 = 6
factorial(4) returns 4 × 6 = 24

Worked examples

Example 1: linear recursion — sum(5)

The method below adds all integers from 1 up to n.

static int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}

Trace of sum(5):

sum(5) = 5 + sum(4)
sum(4) = 4 + sum(3)
sum(3) = 3 + sum(2)
sum(2) = 2 + sum(1)
sum(1) = 1 + sum(0)
sum(0) = 0   ← base case

Unwinding:
sum(1) = 1 + 0 = 1
sum(2) = 2 + 1 = 3
sum(3) = 3 + 3 = 6
sum(4) = 4 + 6 = 10
sum(5) = 5 + 10 = 15

Example 2: branching recursion — fib(5)

The Fibonacci method makes two recursive calls per step, creating a call tree.

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

Key values (computed from base cases up):

fib(0) = 0
fib(1) = 1
fib(2) = fib(1) + fib(0) = 1
fib(3) = fib(2) + fib(1) = 2
fib(4) = fib(3) + fib(2) = 3
fib(5) = fib(4) + fib(3) = 5

Example 3: string recursion

Recursion works just as well on strings. Instead of decrementing an integer, the method shortens the string by one character each call using substring(1), which drops the first character. The base case is an empty string.

The method below counts characters and the one after it reverses a string, both by peeling off one character per call.

static int len(String s) {
    if (s.isEmpty()) return 0;
    return 1 + len(s.substring(1));
}

static String rev(String s) {
    if (s.isEmpty()) return "";
    return rev(s.substring(1)) + s.charAt(0);
}

Trace of len("cat"):

len("cat") = 1 + len("at")
len("at")  = 1 + len("t")
len("t")   = 1 + len("")
len("")     = 0   ← base case

Unwinding:
len("t")   = 1 + 0 = 1
len("at")  = 1 + 1 = 2
len("cat") = 1 + 2 = 3

Trace of rev("cat"):

rev("cat") = rev("at")  + 'c'
rev("at")  = rev("t")   + 'a'
rev("t")   = rev("")    + 't'
rev("")     = ""   ← base case

Unwinding:
rev("t")   = "" + 't'  = "t"
rev("at")  = "t" + 'a' = "ta"
rev("cat") = "ta" + 'c' = "tac"

Notice that rev returns a String, not an int. The practice questions will tell you the return type — read the method signature carefully before you answer.

Avoiding infinite recursion

A recursive method enters infinite recursion when it never reaches its base case. This causes a StackOverflowError in Java. The two most common causes are:

The recursive call does not move the input toward the base case (for example, calling sum(n) instead of sum(n - 1)).
The base case condition is written incorrectly so it is never triggered.

All practice problems on this site use bounded inputs and correct base cases, so every method terminates within ten recursive steps, making them safe to trace by hand without running code.

Refreshable sample

Try one Java recursion question

Need a full set?

Select linear or branching style, then work through the example before checking your answer.

Why tracing recursion matters

Being able to trace recursive code by hand is a foundational skill for technical interviews, algorithm courses, and debugging real programs. It builds intuition for how the call stack grows and shrinks, which helps when writing your own recursive solutions.

Once you are comfortable with linear and branching recursion, you can move on to recursive data structures like trees and graphs, which use the same base-case and unwind pattern at larger scale.

If you also work in Python, the Python recursion tutorial covers the same linear and branching examples — the tracing method is identical, only the syntax changes.

Open Java recursion practice