Java Recursion

Recursion is when a method calls itself. A recursive method solves a problem by reducing it to a smaller version of the same problem, solving that smaller version with the same method, and combining the result. It is the natural fit for data that is itself nested or self-similar: folder trees, organization charts, HTML documents, mathematical sequences, and divide-and-conquer algorithms.

The Two Required Parts

Every correct recursive method has:

1. A base case: an input simple enough to answer directly, without another call. This is what stops the recursion.
2. A recursive case: a call to the same method with an input that is closer to the base case.

static void countdown(int n) {
    if (n == 0) {                 // base case
        System.out.println("Liftoff!");
        return;
    }
    System.out.println(n);
    countdown(n - 1);             // recursive case: smaller input
}

countdown(3);

Output:

3
2
1
Liftoff!

Each call prints its number and calls itself with n - 1. When n reaches 0, the base case prints and returns without another call.

How Recursive Calls Execute

Factorial is the classic example: n! = n × (n−1) × ... × 1, and by definition 0! = 1. It can be stated recursively: n! = n × (n−1)!.

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

System.out.println(factorial(5));     // 120

Every call gets its own stack frame with its own n. The calls stack up until the base case, then return one by one:

factorial(5)
  = 5 * factorial(4)
        = 4 * factorial(3)
              = 3 * factorial(2)
                    = 2 * factorial(1)
                          = 1                <- base case
                    = 2 * 1 = 2
              = 3 * 2 = 6
        = 4 * 6 = 24
  = 5 * 24 = 120

The multiplication n * ... cannot happen until the inner call returns. So the first phase goes down (making calls, each waiting), and the second phase goes back up (each waiting call completes its multiplication). At the deepest point, five frames for factorial exist at once.

Missing or Unreachable Base Case

Without a base case, or when the input never reaches it, a method calls itself until the JVM runs out of stack space:

static int broken(int n) {
    return n + broken(n - 1);     // no base case
}

broken(5);   // java.lang.StackOverflowError

The same happens when the step moves in the wrong direction or skips past the base case:

static long badFactorial(int n) {
    if (n == 1) return 1;
    return n * badFactorial(n - 1);
}

badFactorial(0);    // 0, -1, -2, ... never equals 1 -> StackOverflowError

Using n <= 1 instead of n == 1 covers 0 and guards against negative input. Validating the argument explicitly is even better:

if (n < 0) throw new IllegalArgumentException("n must be non-negative");

Recursion Depth Limits

The JVM stack holds a limited number of frames, typically on the order of several thousand to tens of thousands depending on frame size and the -Xss stack setting. Recursion that goes a million levels deep will throw StackOverflowError even with a correct base case:

static long sumTo(int n) {
    return n == 0 ? 0 : n + sumTo(n - 1);
}

sumTo(10);          // 55
sumTo(1_000_000);   // StackOverflowError

Java does not perform tail-call optimization, so even a recursive call in the last position still uses a new frame. When the depth grows with the size of the input (linearly), prefer a loop:

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

Recursion is safe when the depth grows slowly, such as logarithmically (binary search, balanced trees) or with the nesting depth of real-world data (folder hierarchies rarely exceed a few dozen levels).

Recursion on Strings and Arrays

Reversing a string

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

System.out.println(reverse("java"));   // avaj

Reverse everything after the first character, then put the first character at the end. reverse("java") → reverse("ava") + 'j' → (reverse("va") + 'a') + 'j' → ... → "avaj". (For real use, new StringBuilder(s).reverse().toString() is simpler and faster; this example shows the technique.)

Palindrome check

static boolean isPalindrome(String s, int left, int right) {
    if (left >= right) {
        return true;                                   // met in the middle
    }
    if (s.charAt(left) != s.charAt(right)) {
        return false;                                  // mismatch: stop early
    }
    return isPalindrome(s, left + 1, right - 1);
}

String word = "racecar";
System.out.println(isPalindrome(word, 0, word.length() - 1));   // true

Passing indexes instead of creating substrings avoids copying the string on each call. There are two base cases: success when the indexes meet, failure on the first mismatch.

Binary search

static int binarySearch(int[] sorted, int target, int low, int high) {
    if (low > high) {
        return -1;                                      // not found
    }
    int mid = low + (high - low) / 2;
    if (sorted[mid] == target) {
        return mid;
    } else if (sorted[mid] < target) {
        return binarySearch(sorted, target, mid + 1, high);
    } else {
        return binarySearch(sorted, target, low, mid - 1);
    }
}

int[] data = {3, 8, 15, 23, 42, 57, 91};
System.out.println(binarySearch(data, 42, 0, data.length - 1));   // 4

Each call halves the search range, so even a million-element array needs only about 20 levels. low + (high - low) / 2 avoids the integer overflow that (low + high) / 2 can cause on very large arrays.

Multiple Recursive Calls

A method may call itself more than once. Fibonacci numbers are defined as F(0) = 0, F(1) = 1, and F(n) = F(n−1) + F(n−2):

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

System.out.println(fib(10));   // 55

This mirrors the definition but is extremely slow. fib(5) computes fib(3) twice and fib(2) three times; the number of calls roughly doubles with each increase in n. fib(50) would make billions of calls.

Memoization stores results that have already been computed so each value is calculated only once:

import java.util.HashMap;
import java.util.Map;

static Map<Integer, Long> memo = new HashMap<>();

static long fastFib(int n) {
    if (n < 2) return n;
    Long cached = memo.get(n);
    if (cached != null) return cached;
    long result = fastFib(n - 1) + fastFib(n - 2);
    memo.put(n, result);
    return result;
}

System.out.println(fastFib(90));   // 2880067194370816120

Now each n is computed once, turning exponential work into linear work. This technique is the basis of dynamic programming.

Recursion on Nested Structures

Recursion is most valuable when the data is naturally recursive: a structure that contains smaller structures of the same kind. A folder contains files and other folders; recursion handles any depth without knowing it in advance.

import java.io.File;

static long folderSize(File item) {
    if (item.isFile()) {
        return item.length();                 // base case: a file's own size
    }
    long total = 0;
    File[] children = item.listFiles();
    if (children != null) {                   // null if unreadable
        for (File child : children) {
            total += folderSize(child);       // each subfolder handled the same way
        }
    }
    return total;
}

System.out.println(folderSize(new File("src")) + " bytes");

Writing this with loops alone would require manually managing a stack or queue of folders still to visit. The recursive version follows the shape of the data directly. The same pattern applies to menu trees, category hierarchies, comment threads, JSON documents, and expression parsers.

Recursion Versus Iteration

Any recursive algorithm can be rewritten iteratively, often by using an explicit stack data structure. Choose the form that matches the shape of the problem, and switch to iteration when depth could grow with input size.

Practical Example: Category Tree

An online store organizes products into nested categories. Recursion prints the tree with indentation and counts all products at any depth.

import java.util.List;

public class Categories {
    record Category(String name, int products, List<Category> children) {}

    static void print(Category c, int depth) {
        System.out.println("  ".repeat(depth) + c.name() + " (" + c.products() + ")");
        for (Category child : c.children()) {
            print(child, depth + 1);
        }
    }

    static int totalProducts(Category c) {
        int total = c.products();
        for (Category child : c.children()) {
            total += totalProducts(child);
        }
        return total;
    }

    public static void main(String[] args) {
        Category root = new Category("Electronics", 0, List.of(
            new Category("Phones", 12, List.of(
                new Category("Android", 40, List.of()),
                new Category("iOS", 15, List.of())
            )),
            new Category("Laptops", 25, List.of(
                new Category("Gaming", 8, List.of())
            ))
        ));

        print(root, 0);
        System.out.println("Total products: " + totalProducts(root));
    }
}

Output:

Electronics (0)
  Phones (12)
    Android (40)
    iOS (15)
  Laptops (25)
    Gaming (8)
Total products: 100

The base case is implicit: a category with an empty children list makes no further calls, so the loop body never runs and the method returns. print passes depth + 1 to each child so that indentation grows with nesting. totalProducts adds a category's own count to the totals returned by each child. Neither method knows or cares how deep the tree is; adding another level of subcategories requires no code changes.