[Java Basics] Recursion in Java: How It Works and When to Use It

A recursive method is a method that calls itself with a smaller input. There is no new syntax to learn: a recursive call is an ordinary call, it pushes an ordinary frame, and it returns in the ordinary way. What is new is the discipline that keeps it from running forever.

This article covers that discipline — the base case, the shrinking step, and what the stack looks like while a recursion runs — and then the two things beginners actually get burned by: a StackOverflowError from a missing or unreachable base case, and a naive Fibonacci that makes millions of calls for a number you can compute in dozens. Every number and every error message below is real output from OpenJDK 21.0.6.

Article 19 established that every call pushes a frame holding its own locals, and that the stack has a finite size. Recursion is where that fact stops being trivia and starts being a design constraint.

What recursion actually is

A recursive method has exactly two parts, and both are mandatory:

• a base case: an input the method answers directly, without calling itself;
• a recursive case: everything else, which calls the method on an input that is closer to the base case than the one it received.

Drop the base case and the calls never stop. Keep the base case but hand the recursive call an input that does not shrink, and it never gets there. Either way the stack runs out.

Factorial is the standard first example because both parts are obvious. 0! and 1! are 1 by definition — that is the base case — and n! is n * (n - 1)! for everything above that:

static long factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case, n shrinks by 1
}

Read the second line as a promise rather than as a loop. It says: if someone hands me the answer for n - 1, I can produce the answer for n. The base case is what makes that promise collectable, because the chain of "if someone hands me..." has to end somewhere.

Tracing factorial call by call

Printing on the way in and on the way out makes the two phases visible. This is the single most useful thing you can do when a recursion is not behaving:

public class Factorial {
    static int factorial(int n) {
        System.out.println("enter factorial(" + n + ")");
        if (n <= 1) {
            System.out.println("exit  factorial(" + n + ") -> 1   (base case)");
            return 1;
        }
        int result = n * factorial(n - 1);
        System.out.println("exit  factorial(" + n + ") -> " + result);
        return result;
    }

    public static void main(String[] args) {
        System.out.println("answer = " + factorial(4));
    }
}

enter factorial(4)
enter factorial(3)
enter factorial(2)
enter factorial(1)
exit  factorial(1) -> 1   (base case)
exit  factorial(2) -> 2
exit  factorial(3) -> 6
exit  factorial(4) -> 24
answer = 24

Four enter lines, then four exit lines in the opposite order. That is not a coincidence — it is the call stack. Each enter pushed a frame and the caller stopped to wait; each exit popped one and handed a value to the frame below it.

Two things in that trace are worth naming, because both surprise people:

No multiplication happens on the way down. n * factorial(n - 1) cannot evaluate the * until the call on its right returns. Every frame from factorial(4) to factorial(2) is parked mid-expression, holding its own n, waiting. The first arithmetic in the whole run happens after factorial(1) returns.

The answer is assembled on the way back up. 1, then 2 * 1, then 3 * 2, then 4 * 6. Article 19 showed four frames of four different methods; here the four frames are four calls of the same method, and that changes nothing about how the stack works. Each call has its own n and its own result, in its own frame.

What happens without a base case

The mistake is easy to make and the failure is loud. This method recurses forever because nothing ever stops it:

public class NoBaseCase {
    static int countdown(int n) {
        System.out.println(n);
        return countdown(n - 1);
    }

    public static void main(String[] args) {
        countdown(3);
    }
}

It compiles cleanly — javac has no opinion about whether your recursion terminates. At runtime it counts straight past zero and keeps going:

3
2
1
0
-1
-2
-3

and eventually:

Exception in thread "main" java.lang.StackOverflowError
	at NoBaseCase.countdown(NoBaseCase.java:4)
	at NoBaseCase.countdown(NoBaseCase.java:4)
	at NoBaseCase.countdown(NoBaseCase.java:4)
	at NoBaseCase.countdown(NoBaseCase.java:4)
	at NoBaseCase.countdown(NoBaseCase.java:4)

A stack trace that is the same line repeated hundreds of times is the signature of runaway recursion. Read the repeated line: it names the method and the exact line of the recursive call.

A base case that is never reached

The second shape is nastier, because the base case is right there in the code and looks correct:

public class NotShrinking {
    static int sumTo(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sumTo(n);
    }

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

Exception in thread "main" java.lang.StackOverflowError
	at NotShrinking.sumTo(NotShrinking.java:6)
	at NotShrinking.sumTo(NotShrinking.java:6)
	at NotShrinking.sumTo(NotShrinking.java:6)
	at NotShrinking.sumTo(NotShrinking.java:6)
	at NotShrinking.sumTo(NotShrinking.java:6)

sumTo(n) calls sumTo(n) — the argument was never decremented, so n is 5 in every one of those frames and the n == 0 test never fires. The rule that catches this before you run it: write down what changes between a call and the call it makes, and convince yourself that it moves toward the base case. If nothing changes, you have written an infinite loop with extra steps.

How deep can recursion go?

Deep, but not unboundedly, and the exact number is not a property of the language. Count the frames and find out:

public class Depth {
    static int depth = 0;

    static void dig() {
        depth++;
        dig();
    }

    public static void main(String[] args) {
        try {
            dig();
        } catch (StackOverflowError e) {
            System.out.println("depth reached: " + depth);
        }
    }
}

Three consecutive runs on the same machine, with no options at all:

depth reached: 44286
depth reached: 45378
depth reached: 59567

Three different answers. The default thread stack size varies by platform and JVM build, and even on one machine the count moves between runs. Never write code that relies on a particular recursion depth being available.

You can make the number reproducible by setting the stack size yourself with -Xss. Ten consecutive runs at 256 KB:

for i in $(seq 10); do java -Xss256k Depth; done

depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479
depth reached: 1479

Ten runs, one answer. A larger stack buys more depth, roughly in proportion — -Xss1m reached 20300, 19808 and 19808 on the same machine.

Why the number moves between runs

-Xss512k was not stable at all: 7258, 4793, 6839, 6876, 8989, 5882, 6361, 6918, 6774, 4450. The reason is the JIT compiler. dig is called tens of thousands of times, so partway through the run the JVM recompiles it, and a compiled frame is not the same size as an interpreted one — the frames already on the stack were built by one version and the frames still to come by another. Turning the JIT off proves it:

for i in 1 2 3; do java -Xint -Xss512k Depth; done

depth reached: 4210
depth reached: 4210
depth reached: 4210

At -Xss256k the stack runs out long before the JIT gets interested, which is why that one was stable without -Xint. None of these numbers transfer to another machine, another JDK or another method — a method with more locals uses a bigger frame and overflows sooner.

Six classic recursive methods

Each of these is short on purpose. The point is the shape, not the cleverness:

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

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

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

    static String reverse(String s) {
        if (s.length() <= 1) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    static void countdown(int n) {
        if (n == 0) {
            System.out.println("liftoff");
            return;
        }
        System.out.print(n + " ");
        countdown(n - 1);
    }

    static int binarySearch(int[] a, int target, int lo, int hi) {
        if (lo > hi) return -1;
        int mid = (lo + hi) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) return binarySearch(a, target, mid + 1, hi);
        return binarySearch(a, target, lo, mid - 1);
    }

    public static void main(String[] args) {
        System.out.println("factorial(10) = " + factorial(10));
        System.out.println("sumTo(100)    = " + sumTo(100));
        System.out.println("fib(10)       = " + fib(10));
        System.out.println("reverse       = " + reverse("recursion"));
        countdown(5);
        int[] a = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        System.out.println("index of 23   = " + binarySearch(a, 23, 0, a.length - 1));
        System.out.println("index of 7    = " + binarySearch(a, 7, 0, a.length - 1));
    }
}

factorial(10) = 3628800
sumTo(100)    = 5050
fib(10)       = 55
reverse       = noisrucer
5 4 3 2 1 liftoff
index of 23   = 5
index of 7    = -1

binarySearch is the one worth staring at. It has two base cases — found, and an empty range — and the recursive step throws away half the remaining range rather than one element. That is why it reaches its base case in about 20 calls for a million-element array while sumTo would need a million. The shape of the shrinking step decides everything.

Why naive Fibonacci is a trap

fib above is the textbook recursive definition and it is correct. It is also the standard example of recursion done catastrophically badly, and you can see exactly why by counting the calls:

public class FibCount {
    static long calls = 0;

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

    static long memoCalls = 0;

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

    public static void main(String[] args) {
        System.out.println("  n |        fib(n) |   naive calls | memoised calls");
        for (int n : new int[] {10, 20, 30, 40}) {
            calls = 0;
            long v = fib(n);
            memoCalls = 0;
            long m = fibMemo(n, new long[n + 1]);
            System.out.printf("%3d | %13d | %13d | %14d%n", n, v, calls, memoCalls);
            if (v != m) throw new AssertionError("mismatch at " + n);
        }
    }
}

  n |        fib(n) |   naive calls | memoised calls
 10 |            55 |           177 |             19
 20 |          6765 |         21891 |             39
 30 |        832040 |       2692537 |             59
 40 |     102334155 |     331160281 |             79

Those are call counts, not timings, so they are the same on your machine as on mine. fib(30) returns a six-digit number after 2,692,537 method calls. fib(40) needs 331,160,281.

The growth rate is often described as "the count doubles each time you add one to n". It does not, quite. Counting the calls for every n from 5 to 30 and dividing each count by the previous one, the ratio settles at 1.618 — the golden ratio — so the count more than doubles for every two steps. Five rows from that run:

n=10  calls=      177  ratio to n-1 = 1.624
n=15  calls=     1973  ratio to n-1 = 1.619
n=20  calls=    21891  ratio to n-1 = 1.618
n=25  calls=   242785  ratio to n-1 = 1.618
n=30  calls=  2692537  ratio to n-1 = 1.618

The cause is not recursion. The cause is that the same subproblem is solved over and over. fib(5) needs the answers to only six distinct subproblems, fib(0) through fib(5), and makes 15 calls to get them:

naive fib(5): 15 calls, per node {0=3, 1=5, 2=3, 3=2, 4=1, 5=1}
memo  fib(5): 9 calls

fib(3) is computed twice, fib(2) three times, fib(1) five times. Every one of those recomputations drags its whole subtree along with it, and that is where the 1.618 comes from.

Memoisation: remember what you already computed

The fix is four lines and one array. Before recursing, check whether the answer is already known; after computing it, write it down:

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

fib(10) = 55                   in 19 calls (2n-1 = 19)
fib(20) = 6765                 in 39 calls (2n-1 = 39)
fib(30) = 832040               in 59 calls (2n-1 = 59)
fib(40) = 102334155            in 79 calls (2n-1 = 79)
fib(90) = 2880067194370816120  in 179 calls (2n-1 = 179)

Exactly 2n - 1 calls, every time: each of the n subproblems is solved once and looked up once. Side by side:

The memo[n] != 0 test works here only because no Fibonacci number except fib(0) is zero, and fib(0) is handled by the base case above it. For a problem where zero is a legitimate answer, use a separate boolean[] of "already computed" flags or a Long[] and test for null.

⚠️ Slow recursive code is almost never slow because of the calls. It is slow because it is solving the same subproblem repeatedly. Count the calls before you rewrite anything.

Recursion versus iteration

Anything you can write recursively you can write as a loop, and vice versa. Here is the same sum both ways, with a counter in each:

public class RecVsIter {
    static long calls = 0;
    static long steps = 0;

    static long sumRec(int n) {
        calls++;
        if (n == 0) return 0;
        return n + sumRec(n - 1);
    }

    static long sumIter(int n) {
        long total = 0;
        for (int i = 1; i <= n; i++) {
            steps++;
            total += i;
        }
        return total;
    }

    public static void main(String[] args) {
        for (int n : new int[] {5, 100, 10000}) {
            calls = 0;
            steps = 0;
            long r = sumRec(n);
            long it = sumIter(n);
            System.out.printf("n = %-5d  recursive: %5d calls, %5d frames deep -> %d%n", n, calls, calls, r);
            System.out.printf("           iterative: %5d loop steps, 1 frame     -> %d%n", steps, it);
        }
        System.out.println();
        try {
            System.out.println("sumRec(1000000)  = " + sumRec(1000000));
        } catch (StackOverflowError e) {
            System.out.println("sumRec(1000000)  threw " + e);
        }
        System.out.println("sumIter(1000000) = " + sumIter(1000000));
    }
}

n = 5      recursive:     6 calls,     6 frames deep -> 15
           iterative:     5 loop steps, 1 frame     -> 15
n = 100    recursive:   101 calls,   101 frames deep -> 5050
           iterative:   100 loop steps, 1 frame     -> 5050
n = 10000  recursive: 10001 calls, 10001 frames deep -> 50005000
           iterative: 10000 loop steps, 1 frame     -> 50005000

sumRec(1000000)  threw java.lang.StackOverflowError
sumIter(1000000) = 500000500000

Same answers, and roughly the same amount of arithmetic. The difference is where the work is held: the recursive version needs n + 1 live frames simultaneously, the loop needs one frame and two local variables. At a million, that difference stops being aesthetic.

The honest summary: for a straight count from 1 to n, the loop is better and there is no argument to have. For anything whose shape is a tree, recursion is usually the shorter and clearer code, and the explicit-stack alternative is what you fall back to when the depth is genuinely unbounded.

Rewriting a recursion with an explicit stack

"Every recursion can be rewritten iteratively" is true, but it does not mean "rewritten as a for loop". What you actually do is take over the job the call stack was doing. Here is a tree walk done with an ArrayDeque standing in for the frames:

import java.io.File;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class WalkIterative {
    record Entry(File file, String indent) {}

    static void walk(File root) {
        Deque<Entry> stack = new ArrayDeque<>();
        stack.push(new Entry(root, ""));
        while (!stack.isEmpty()) {
            Entry e = stack.pop();
            System.out.println(e.indent() + e.file().getName() + (e.file().isDirectory() ? "/" : ""));
            File[] entries = e.file().listFiles();
            if (entries == null) continue;
            Arrays.sort(entries);
            for (int i = entries.length - 1; i >= 0; i--) {
                stack.push(new Entry(entries[i], e.indent() + "    "));
            }
        }
    }

    public static void main(String[] args) {
        walk(new File("project"));
    }
}

That produces byte-for-byte the same output as the recursive walk in the next section, and it cannot overflow the call stack because the pending work lives on the heap instead. It is also visibly more code, and the for loop that pushes children in reverse order exists purely to get the traversal order back. That trade — more code, no depth limit — is the whole reason the rewrite exists.

Tail recursion and why Java does not optimise it

A call is in tail position when it is the last thing the method does: its result is returned directly, with no pending work waiting for it. countdown below is tail recursive; factorial is not, because a multiplication is still owed when the recursive call returns.

In languages that guarantee tail-call optimisation, a compiler may turn a tail call into a jump and reuse the frame, so the recursion runs in constant stack space. Java makes no such guarantee, and HotSpot does not do it. The bytecode says so plainly — this is javap -c on a tail-recursive countdown:

  static void countdown(int);
    Code:
       0: getstatic     #7                  // Field calls:J
       3: lconst_1
       4: ladd
       5: putstatic     #7                  // Field calls:J
       8: iload_0
       9: ifne          13
      12: return
      13: iload_0
      14: iconst_1
      15: isub
      16: invokestatic  #13                 // Method countdown:(I)V
      19: return

Offset 16 is an invokestatic — a real method call that pushes a real frame — followed by a return at 19. javac emitted a call, not a jump back to offset 0. And the JVM behaves accordingly:

public class TailDepth {
    static long calls = 0;

    static void countdown(int n) {
        calls++;
        if (n == 0) return;
        countdown(n - 1);
    }

    public static void main(String[] args) {
        try {
            countdown(1000000);
            System.out.println("finished, calls = " + calls);
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError after " + calls + " calls");
        }
    }
}

StackOverflowError after 1267 calls
StackOverflowError after 1267 calls
StackOverflowError after 1267 calls
StackOverflowError after 1267 calls
StackOverflowError after 1267 calls

That is five runs with -Xss256k. On the default stack the same program failed after 31256, 32573 and 32101 calls. Either way it fails: a tail-recursive method in Java consumes one frame per call exactly like any other, so writing a recursion in tail form buys you nothing in Java. If the depth is the problem, the fix is a loop, not a rearrangement of the recursive call.

Mutual recursion

Recursion does not have to be a method calling itself directly. Two methods can call each other, which is called mutual recursion. Each still needs a base case:

public class EvenOdd {
    static boolean isEven(int n) {
        if (n == 0) return true;
        return isOdd(n - 1);
    }

    static boolean isOdd(int n) {
        if (n == 0) return false;
        return isEven(n - 1);
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 5; n++) {
            System.out.println(n + ": isEven=" + isEven(n) + ", isOdd=" + isOdd(n));
        }
    }
}

0: isEven=true, isOdd=false
1: isEven=false, isOdd=true
2: isEven=true, isOdd=false
3: isEven=false, isOdd=true
4: isEven=true, isOdd=false
5: isEven=false, isOdd=true

This particular pair is a demonstration, not advice — n % 2 == 0 is the real answer and costs no frames. Mutual recursion earns its keep in parsers and interpreters, where the grammar itself is mutually recursive: an expression contains terms, and a term can contain a parenthesised expression.

Recursion over structures, not numbers

Every example so far shrank a number, and for numbers a loop is usually the better tool. Recursion pays for itself when the data is nested and you do not know how deep it goes. A directory tree is the standard case:

import java.io.File;
import java.util.Arrays;

public class WalkTree {
    static void walk(File dir, String indent) {
        File[] entries = dir.listFiles();
        if (entries == null) return;
        Arrays.sort(entries);
        for (File f : entries) {
            System.out.println(indent + f.getName() + (f.isDirectory() ? "/" : ""));
            if (f.isDirectory()) {
                walk(f, indent + "    ");
            }
        }
    }

    public static void main(String[] args) {
        File root = new File("project");
        System.out.println(root.getName() + "/");
        walk(root, "    ");
    }
}

Run against a small tree with project/README.md, project/docs/guide.md, project/src/main/App.java, project/src/main/Util.java and project/src/test/AppTest.java:

project/
    README.md
    docs/
        guide.md
    src/
        main/
            App.java
            Util.java
        test/
            AppTest.java

Notice what is not in that method: no stack, no queue, no list of directories still to visit, no depth counter. The base case is "a directory with no entries, or something that is not a directory" and it is expressed by the for loop simply not running. The recursive case is "for each subdirectory, do the same thing one level deeper".

Try writing that as a plain loop and you immediately need somewhere to keep the directories you have not opened yet — which is the ArrayDeque version above, and which is just the call stack rebuilt by hand. That is the honest test for whether recursion is the right choice: if the iterative version needs a stack of its own, use recursion.

When to use recursion and when not to

The depth argument is the one that decides most real cases. Divide-and-conquer recursion over a million elements is about 20 frames deep and perfectly safe; linear recursion over a million elements is a million frames deep and is not.

Common mistakes and the output they produce

The third one is the dangerous member of that list, because nothing fails. 0! is 1, not 0, and getting that wrong poisons every result:

public class BadBaseCase {
    /* Wrong: the base case answers 0 for n = 0, so every product collapses. */
    static long factorialWrong(int n) {
        if (n == 0) return 0;
        return n * factorialWrong(n - 1);
    }

    /* Right: 0! is 1, the identity for multiplication. */
    static long factorialRight(int n) {
        if (n == 0) return 1;
        return n * factorialRight(n - 1);
    }

    public static void main(String[] args) {
        for (int n = 0; n <= 5; n++) {
            System.out.println("n=" + n + "  wrong=" + factorialWrong(n) + "  right=" + factorialRight(n));
        }
    }
}

n=0  wrong=0  right=1
n=1  wrong=0  right=1
n=2  wrong=0  right=2
n=3  wrong=0  right=6
n=4  wrong=0  right=24
n=5  wrong=0  right=120

Every answer is 0, because every product eventually multiplies by the base case. There is no exception, no warning and no stack trace to read — just wrong numbers. Always evaluate your base case by hand before trusting the recursion above it.

FAQ

Is recursion slower than a loop in Java?

A call is not free — it pushes a frame, and a loop iteration does not — but that overhead is small and the JIT can inline shallow recursive calls. In practice, recursive code that is slow is slow for one of two reasons that have nothing to do with call overhead: it is recomputing subproblems it has already solved, or it is doing more total work than the iterative version. Count the calls first; that number is reproducible and it usually explains everything.

How deep can a recursion go in Java?

There is no language-defined limit. It depends on the thread stack size, the size of each frame, the platform and the JVM build. Measured here: about 44000 to 59000 frames on the default stack across three runs, a stable 1479 with -Xss256k, and about 20000 with -Xss1m. Treat any specific number as a measurement of one machine on one day, not as a constant.

Does the JVM optimise tail recursion?

No. The Java language makes no tail-call guarantee and HotSpot does not eliminate tail calls, so a tail-recursive method still pushes a frame per call and still overflows — proved above with javap output showing an invokestatic in tail position and a run that failed after 1267 calls. If you need constant stack space, write a loop.

Can I catch StackOverflowError?

Syntactically yes: it is a Throwable, so catch (StackOverflowError e) compiles and runs, as the depth-counting program above relies on. In real code it is a bad idea. It is an Error, meaning the JVM is signalling a condition your program is not expected to recover from, and you have no way to know what state the half-unwound stack left things in. Catch it in a diagnostic, never in production logic.

Should I just increase -Xss when I get a StackOverflowError?

Occasionally that is the right answer, for a genuinely deep tree or a library that recurses per input element. Far more often the overflow is a bug — a missing base case, or a step that does not shrink — and a bigger stack only delays it. Look at the stack trace first: a small set of lines repeating thousands of times means a bug, while a long trace of many different methods means you really are that deep.

How do I convert a recursion into a loop?

If the recursion is linear, like sumTo or a tail-recursive countdown, a plain for or while loop with an accumulator does it directly. If it branches, like a tree walk, you need an explicit stack — push the root, then repeatedly pop an item, process it and push its children, as the ArrayDeque version above does. The rule of thumb: whatever the frames were remembering for you, you now have to remember yourself.

Conclusion

Recursion is a method calling itself on a smaller input, and it needs exactly two things to work: a base case that returns without recursing, and a recursive case that moves toward it. Everything that goes wrong comes from breaking one of those — no base case, a step that does not shrink, or a base case returning the wrong value — and the first two announce themselves as a StackOverflowError with one line repeated down the trace. Depth is bounded by the stack, machine-dependent, and unaffected by writing the call in tail position, because the JVM does not eliminate tail calls. And when a recursion is slow, count the calls: 2,692,537 for fib(30) against 59 memoised is the whole story of why the naive version is a trap.

Where recursion genuinely wins is data whose shape is nested and whose depth is unknown — a directory tree, a parse tree, a JSON document. The test is simple: if writing the loop would force you to build a stack of your own, the call stack is already doing that job for you.

The next article leaves procedural Java behind and starts on objects: what a class is, what an object is, how new builds one, and what fields, constructors and this actually mean — the point where the static you have been writing on every method finally has an alternative.