Recursion II: Helper Methods, Backtracking and Memoization

A two-line reminder

A recursive method solves a problem by calling itself on a smaller instance and stops at a base case; every pending call waits in its own frame on the call stack. You met this in CPS 2231 with factorial, fib and digit sums — this chapter is about what you do next.

A stack frame is the small block of memory that one call uses for its parameters and local variables. While a call waits for the answer of a smaller call, its frame stays on the call stack (like a plate in a pile). When the call returns, its frame is removed.

Every correct recursive method answers two questions:

1. Base case — when is the problem so small that I can answer directly?
2. Recursive step — how do I make the problem smaller, and how do I use the smaller answer?

Recursive helper methods

Many problems are recursive on a part of the input: the characters between lo and hi, the array from index i onwards. Instead of building smaller copies (substring, Arrays.copyOfRange), pass indices to a helper. The public method keeps a clean signature; the private helper carries the extra parameters.

public static boolean isPalindrome(String s) {
    return isPalindrome(s, 0, s.length() - 1);       // start the helper
}

private static boolean isPalindrome(String s, int lo, int hi) {
    if (lo >= hi) return true;                         // 0 or 1 characters left
    if (s.charAt(lo) != s.charAt(hi)) return false;
    return isPalindrome(s, lo + 1, hi - 1);            // shrink from both ends
}

Worked example. A palindrome reads the same forwards and backwards. Call isPalindrome("racecar"). The string never changes; only the two indices move towards each other.

index:  0 1 2 3 4 5 6
        r a c e c a r
        ^           ^
        lo          hi

Step	Call	Compare	What happens
1	isPalindrome("racecar", 0, 6)	r and r	equal → move both ends inwards
2	isPalindrome("racecar", 1, 5)	a and a	equal → move inwards
3	isPalindrome("racecar", 2, 4)	c and c	equal → move inwards
4	isPalindrome("racecar", 3, 3)	—	lo >= hi: base case, return true

The true travels back through the three waiting calls, so the answer is true. With "abca" the second call compares b and c, returns false at once, and no more calls are made.

Each call does O(1) work, so the whole check is O(n). The version that calls s.substring(1, s.length() - 1) copies the string at every level: O(n²) time and memory.

Recursion on arrays and strings

The typical shape is "handle position i, recurse on i + 1":

static int sum(int[] a, int i) {
    if (i == a.length) return 0;          // empty suffix
    return a[i] + sum(a, i + 1);
}

static String reverse(String s, int i) {
    if (i == s.length()) return "";
    return reverse(s, i + 1) + s.charAt(i);   // work done AFTER the call
}

A suffix is the part of the array from i to the end. sum(new int[]{3, 1, 4}, 0) is 3 + (1 + (4 + 0)) = 8.

Worked example: reverse("abc", 0). Read the drawing from top to bottom: first the calls go down (nobody can finish yet), then the answers come back up.

reverse("abc", 0)                 waits for reverse(1), then adds 'a'
  reverse("abc", 1)               waits for reverse(2), then adds 'b'
    reverse("abc", 2)             waits for reverse(3), then adds 'c'
      reverse("abc", 3)           base case: returns ""
    returns "" + 'c'   = "c"
  returns "c" + 'b'    = "cb"
returns "cb" + 'a'     = "cba"

Whether the work happens before or after the recursive call decides the order of the output. In reverse the character is appended on the way back, so the last character comes first.

Recursive binary search

Binary search on a sorted array is naturally recursive: look at the middle, then search one half.

public static int search(int[] a, int key) {
    return search(a, key, 0, a.length - 1);
}

private static int search(int[] a, int key, int low, int high) {
    if (low > high) return -1;                        // empty range: not found
    int mid = (low + high) / 2;
    if (a[mid] == key) return mid;
    if (a[mid] < key) return search(a, key, mid + 1, high);
    return search(a, key, low, mid - 1);
}

Worked example. The array has 7 elements:

index:  0   1   2   3   4   5   6
value:  2   5   8  12  16  23  38

Search for 23:

Step	low	high	mid	a[mid]	Decision
1	0	6	3	12	12 < 23 → search the right half (low = 4)
2	4	6	5	23	found → return 5

Search for 7 (not in the array):

Step	low	high	mid	a[mid]	Decision
1	0	6	3	12	12 > 7 → search the left half (high = 2)
2	0	2	1	5	5 < 7 → search the right part (low = 2)
3	2	2	2	8	8 > 7 → high = 1
4	2	1	—	—	low > high: empty range, return −1

Only 4 calls for 7 elements. With 1,000,000 elements you would need only about 20.

The range halves at every call, so there are at most about log₂ n + 1 calls: O(log n) time and O(log n) stack depth.

Recursion versus iteration

Anything written recursively can be written with a loop (and, if needed, an explicit stack), and vice versa.

	Recursion	Iteration
Fits naturally	trees, divide-and-conquer, backtracking	simple scans, counting loops
Extra memory	one stack frame per pending call	usually O(1)
Risk	StackOverflowError when depth is large	off-by-one in loop bounds

A method whose recursive call is the very last action (tail recursion, like isPalindrome above) converts directly into a while loop. Java does not perform tail-call elimination, so even tail recursion uses one frame per call.

Here is the palindrome check as a loop. The parameters lo and hi simply become local variables that change at the end of each round:

static boolean isPalindromeLoop(String s) {
    int lo = 0, hi = s.length() - 1;
    while (lo < hi) {                                  // the base case becomes the loop condition
        if (s.charAt(lo) != s.charAt(hi)) return false;
        lo++;                                          // the recursive call becomes
        hi--;                                          // "update the variables and repeat"
    }
    return true;
}

reverse is not tail recursive: after the call returns, it still has to append a character.

The cost of naive recursion

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

This is correct but slow, because the same sub-problems are solved again and again: fib(5) computes fib(3) twice and fib(2) three times. The recursion tree shows every call as a node, with its two calls below it:

                          fib(5)
                /                      \
           fib(4)                      fib(3)
         /        \                   /      \
     fib(3)       fib(2)          fib(2)     fib(1)
     /    \       /    \          /    \
 fib(2) fib(1) fib(1) fib(0)  fib(1) fib(0)
 /    \
fib(1) fib(0)

Count the nodes: 15 calls. The whole right sub-tree fib(3) is a repeat of work already done on the left.

If C(n) is the number of calls, then C(0) = C(1) = 1 and C(n) = C(n−1) + C(n−2) + 1:

n	5	10	20	40
calls	15	177	21 891	331 160 281

The growth is exponential (about 1.618ⁿ). Two calls per level on problems that shrink by only 1 or 2 is the warning sign.

Memoization

Memoization stores each result the first time it is computed and returns the stored value on every later call. Each distinct sub-problem is then solved once.

static long[] memo = new long[91];            // 0 means "not computed yet"

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

(The array has 91 slots, so it works for n from 0 to 90. The values grow so fast that fib(93) no longer fits in a long anyway.)

Worked example: fib(6) with a memo. The calls go down the left side first (fib(6) → fib(5) → … → fib(2)). Then the notes are filled in from small to large:

Step	Event	memo[2..6] after the step
1	fib(2) = fib(1) + fib(0) = 1 + 0, store	[1, -, -, -, -]
2	fib(3) = fib(2) + fib(1) = 1 + 1, store	[1, 2, -, -, -]
3	fib(4) asks for fib(2) → found on a note (1)	[1, 2, -, -, -]
4	fib(4) = 2 + 1, store	[1, 2, 3, -, -]
5	fib(5) asks for fib(3) → found (2)	[1, 2, 3, -, -]
6	fib(5) = 3 + 2, store	[1, 2, 3, 5, -]
7	fib(6) asks for fib(4) → found (3)	[1, 2, 3, 5, -]
8	fib(6) = 5 + 3, store	[1, 2, 3, 5, 8]

Result: 8, using 11 calls instead of the 25 calls of the naive version. For fib(40) the difference is 79 calls against 331 million.

When the arguments are not small integers (or 0 is a legal answer), use a HashMap:

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

static long ways(int n) {                     // climb n stairs taking 1 or 2 steps
    if (n <= 1) return 1;
    if (memo.containsKey(n)) return memo.get(n);
    long result = ways(n - 1) + ways(n - 2);
    memo.put(n, result);                      // forget this line and nothing is saved
    return result;
}

With memoization fib(n) runs in O(n) time with O(n) extra memory. Memoization is top-down dynamic programming; the bottom-up (table-filling) style comes later in the course.

The memo pattern is always the same three lines: look up (return if known) → compute → store and return.

Backtracking

Backtracking builds a solution one decision at a time and abandons (backs up from) a partial solution as soon as it cannot lead anywhere. Every backtracking method follows the same template:

void explore(state) {
    if (state is complete) { record or print it; return; }
    for (each possible choice) {
        if (choice is allowed) {
            make the choice;          // choose
            explore(new state);       // explore
            undo the choice;          // un-choose
        }
    }
}

Subsets — at each index decide "take it" or "leave it". There are 2ⁿ leaves:

static void subsets(int[] a, int i, List<Integer> chosen) {
    if (i == a.length) { System.out.println(chosen); return; }
    chosen.add(a[i]);                         // choose: take a[i]
    subsets(a, i + 1, chosen);
    chosen.remove(chosen.size() - 1);         // un-choose
    subsets(a, i + 1, chosen);                // leave a[i]
}

Worked example: subsets({1, 2, 3}, 0, []). Each level makes one decision about one number. Left branch = take it, right branch = leave it.

                              []                        i = 0: decide about 1
                 take 1 /          \ leave 1
                    [1]                  []             i = 1: decide about 2
           take 2 /     \ leave     take /  \ leave
             [1,2]       [1]         [2]      []        i = 2: decide about 3
             /   \       /  \        /  \     /  \
       [1,2,3] [1,2]  [1,3] [1]  [2,3] [2]  [3]  []      i = 3: print

The leaves are printed from left to right:

[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]

Look at the moment between [1, 2, 3] and [1, 2]: the method printed [1, 2, 3], returned, and then chosen.remove(...) took the 3 out again. That is the un-choose step. Without it, the list would keep growing: for {1, 2} the version without the remove prints [1, 2], [1, 2], [1, 2, 2], [1, 2, 2] — wrong.

Permutations — at each level pick one of the remaining items. There are n! results:

static void perms(String done, String rest) {
    if (rest.isEmpty()) { System.out.println(done); return; }
    for (int i = 0; i < rest.length(); i++)
        perms(done + rest.charAt(i), rest.substring(0, i) + rest.substring(i + 1));
}

Worked example: perms("", "abc"). done is what you have already placed; rest is what you may still use.

perms("", "abc")
├── perms("a", "bc")
│   ├── perms("ab", "c") ── perms("abc", "")  → print abc
│   └── perms("ac", "b") ── perms("acb", "")  → print acb
├── perms("b", "ac")
│   ├── perms("ba", "c") ── perms("bac", "")  → print bac
│   └── perms("bc", "a") ── perms("bca", "")  → print bca
└── perms("c", "ab")
    ├── perms("ca", "b") ── perms("cab", "")  → print cab
    └── perms("cb", "a") ── perms("cba", "")  → print cba

3 choices, then 2, then 1: 3 × 2 × 1 = 3! = 6 results.

Here no explicit undo is needed because done + ... creates a new string for each call; when the state is a shared mutable object (a list, a board, a visited array) you must undo.

N-Queens — place one queen per row; for each column, check the queens already placed:

static int solutions = 0;

static void place(int[] col, int row) {       // col[r] = column of the queen in row r
    int n = col.length;
    if (row == n) { solutions++; return; }
    for (int c = 0; c < n; c++) {
        if (safe(col, row, c)) {
            col[row] = c;                     // choose (overwritten by the next try)
            place(col, row + 1);
        }
    }
}

static boolean safe(int[] col, int row, int c) {
    for (int r = 0; r < row; r++)
        if (col[r] == c || Math.abs(col[r] - c) == row - r) return false;  // column or diagonal
    return true;
}

A queen attacks along its column and its two diagonals. Two queens are on the same diagonal when the column distance equals the row distance — that is the test Math.abs(col[r] - c) == row - r.

Worked example: the 4×4 board. Follow the first attempts (Q = queen, x = attacked square in the current row):

Step 1: row 0, col 0      Step 2: row 1, col 2      Step 3: row 2 — all 4
                          (cols 0, 1 attacked)      columns attacked → BACK
Q . . .                   Q . . .                   Q . . .
. . . .                   . . Q .                   . . Q .
. . . .                   . . . .                   x x x x
. . . .                   . . . .                   . . . .

Step 4: move row 1        Step 5: row 2, col 1      Step 6: row 3 — all 4
to col 3                                            attacked → BACK
Q . . .                   Q . . .                   Q . . .
. . . Q                   . . . Q                   . . . Q
. . . .                   . Q . .                   . Q . .
. . . .                   . . . .                   x x x x

No placement works with a queen at column 0 of row 0, so the method backs up all the way to row 0 and tries column 1. That branch finds the first solution, col = [1, 3, 0, 2]; the branch with column 2 finds the second, [2, 0, 3, 1]:

Solution 1: [1, 3, 0, 2]     Solution 2: [2, 0, 3, 1]
. Q . .                      . . Q .
. . . Q                      Q . . .
Q . . .                      . . . Q
. . Q .                      . Q . .

Rows never clash because each row receives exactly one queen. The 4×4 board has 2 solutions, 8×8 has 92. Pruning (rejecting a column as soon as it is attacked) is what makes backtracking far faster than trying all nⁿ placements.

Why is there no explicit un-choose here? Because col[row] is simply overwritten by the next column you try, and safe only reads rows 0 to row - 1, so an old value left in a later row does no harm. The array acts as the "undo" by itself.

A maze search is the same idea on a grid: mark the cell as visited, try the four neighbours, and unmark it when you return so that other paths may use it.

Depth and StackOverflowError

Every pending call keeps a frame on the thread's stack, which is small (typically a few thousand to tens of thousands of frames, depending on the frame size and the JVM settings). A recursion that is too deep, or that never reaches its base case, ends with java.lang.StackOverflowError.

• StackOverflowError is an Error, not an Exception: catch (Exception e) does not catch it.
• Recursing once per element (sum(a, i + 1)) on a million-element array will overflow; recursing on halves (depth log₂ n ≈ 20) will not.
• If depth can be large, rewrite the method with a loop, or use an explicit stack.

Method	Calls made (time)	Maximum depth (memory)
sum(a, 0) on n elements	n + 1	n + 1
recursive binary search	about log₂ n	about log₂ n
naive fib(n)	exponential (≈ 1.618ⁿ)	n
memoized fib(n)	about 2n	n
subsets of n items	about 2ⁿ⁺¹	n + 1

Key takeaways

• Every recursive method needs a base case and a step that makes the problem smaller.
• Use a public method + private helper: the helper carries indices, totals or the partial answer, so you never copy arrays or strings.
• Code before the recursive call runs on the way down; code after it runs on the way back (this is why reverse works).
• Recursive binary search halves the range each time: O(log n) calls. Always write mid + 1 / mid - 1 and the low > high base case.
• Naive fib is exponential because sub-problems overlap. Memoization (look up → compute → store) makes it O(n).
• Backtracking = choose → explore → un-choose. Undo every change to a shared list, board or visited array; prune as early as possible.
• Subsets give 2ⁿ results, permutations give n! results; 4-Queens has 2 solutions, 8-Queens has 92.
• StackOverflowError is an Error, not an Exception. Deep one-element-per-call recursion should become a loop.