Stage 1: Java fundamentals, lesson 10 of 10

Recursion

Beginner3 min read@since 16Code runs on your Java 25
Explain it forThe essentials plus production detail and pitfalls.

A recursive method calls itself on a smaller version of the problem. Every recursive method needs:

  1. A base case that returns without recursing.
  2. A recursive case that moves towards the base case.

Recursion fits problems that are naturally self-similar: folders inside folders, tree structures, and divide-and-conquer algorithms such as merge sort.

Each call adds a frame to the call stack. Too many nested calls, or a missing base case, ends in StackOverflowError. Java doesn't optimise tail calls, so very deep recursion should become a loop.

Naive recursion can repeat work: the classic Fibonacci recomputes the same values again and again. Memoization, remembering results you've already computed, fixes that and leads straight into dynamic programming.

Example

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

static long fib(int n, Map<Integer, Long> memo) {
    if (n <= 1) return n;
    Long cached = memo.get(n);
    if (cached != null) return cached;
    long value = fib(n - 1, memo) + fib(n - 2, memo);
    memo.put(n, value);
    return value;
}

static long folderSize(Path dir) throws IOException {     // natural recursion
    long total = 0;
    try (var entries = Files.list(dir)) {
        for (Path p : entries.toList()) {
            total += Files.isDirectory(p) ? folderSize(p) : Files.size(p);
        }
    }
    return total;
}

System.out.println(factorial(5));               // 120
System.out.println(fib(50, new HashMap<>()));   // 12586269025, instantly

Common mistake

Forgetting the base case, or writing one the recursion never reaches (for example calling fib(n + 1)). The result is StackOverflowError.

Under the hood

The stack size per thread is set with -Xss and typically allows a few thousand frames. Any recursion can be rewritten with an explicit stack (ArrayDeque) and a loop, which is how production code walks very deep trees; Files.walk does this for directories.

Check yourself

What must every recursive method have?

How this connects

Part of Java from zero.

Was this lesson helpful?

Finished reading? Mark it complete to track your progress.