Recursion pitfalls

With no base case, or a base case the input never reaches, the method calls itself until the stack is exhausted. A frequent variant is checking n == 0 when n can jump over 0 (for example n -= 2 from an odd n).

Use <= or an explicit range check for the base case when the argument can skip values, and write down the shrinking quantity before coding.

1static int countDown(int n) {
2    if (n == 0) return 0;              // bug: countDown(5 - 2 - 2 - 2) skips 0 and goes negative
3    return countDown(n - 2);
4}
5
6static int countDownFixed(int n) {
7    if (n <= 0) return 0;              // fix: any non-positive value stops the recursion
8    return countDownFixed(n - 2);
9}

A recursive call returns a value, and ignoring it is a common bug: calling sum(n - 1) without using or returning the result computes the right thing and throws it away.

In a method that returns a value from every branch, make sure each recursive path returns. In a search that tries several branches, only return true immediately, and fall through to false after all branches fail.

1static int sumTo(int n) {
2    if (n == 0) return 0;
3    int rest = sumTo(n - 1);           // computed...
4    return n;                          // ...but never used: returns n instead of n + rest
5}
6
7static int sumToFixed(int n) {
8    if (n == 0) return 0;
9    return n + sumToFixed(n - 1);      // the recursive result is used and returned
10}

When recursive calls modify the same array, list or counter, later calls see earlier changes. That is intended in backtracking, but only if you undo each change after the call. Forgetting to remove an element from a path list, or adding the same list object to the results instead of a copy, are the typical bugs.

Pass state as parameters or return values where you can. If you must share it, copy before you store (new ArrayList<>(path)) and undo after you recurse (path.remove(path.size() - 1)).

1static void subsets(int[] a, int i, List<Integer> path, List<List<Integer>> out) {
2    if (i == a.length) { out.add(new ArrayList<>(path)); return; }   // copy: path keeps changing
3    path.add(a[i]);                  // choose
4    subsets(a, i + 1, path, out);
5    path.remove(path.size() - 1);    // undo, so the other branch starts clean
6    subsets(a, i + 1, path, out);
7}

When two branches of the recursion tree solve the same subproblem, the algorithm repeats work and may become exponential. Naive Fibonacci recomputes fib(2) five times for n = 6. The same happens in naive grid-path counting, coin change and edit distance.

The signs are overlapping subproblems and a recursion tree with identical nodes. The fix is to cache results: top-down memoization or bottom-up dynamic programming (Chapter 23).

Java throws StackOverflowError when the thread's call stack is full. The limit is typically a few thousand to tens of thousands of frames, depending on frame size and the -Xss setting. A recursion on a list of 100,000 elements can easily exceed it.

Fixes: make sure there is a base case, reduce depth by halving instead of subtracting, convert to an iterative loop or explicit stack, or run the work in a thread with a bigger stack. Do not catch the error as a normal control path.

1// deep work in a thread with a 256 MB stack
2Thread worker = new Thread(null, () -> solve(), "deep", 256L * 1024 * 1024);
3worker.start();

Recursive results can grow quickly: factorial, powers and Fibonacci all exceed int within a few dozen steps. Overflow wraps silently in Java and gives plausible but wrong numbers.

Use long, BigInteger, or modular arithmetic, and use Math.addExact or Math.multiplyExact where you want an exception instead of a silent wrap. Midpoints in divide and conquer should be lo + (hi - lo) / 2.

1int ok  = 12 * 11 * 10;                      // fine
2int bad = 13 * 479_001_600;                  // wraps to 1932053504, not 6227020800
3long good = 13L * 479_001_600L;              // 6227020800
4long safe = Math.multiplyExact(13L, 479_001_600L);   // throws ArithmeticException on overflow