Thinking recursively

Written Explanation

The recipe

To write a recursive method, answer three questions in order:

1. Base case: what is the smallest version of the problem, whose answer I know immediately?
2. Smaller step: how do I turn a bigger problem into a slightly smaller one of the same kind?
3. Combine: if I trust that the smaller call returns the right answer, what do I do with it to get the answer for the bigger problem?

Take the sum of the digits of a non-negative number, such as 4821 giving 4 + 8 + 2 + 1 = 15.

1. Base case: a number with a single digit (n < 10) has a digit sum equal to itself.
2. Smaller step: n / 10 removes the last digit (integer division); n % 10 is that last digit.
3. Combine: digit sum of n = last digit + digit sum of the rest.

static int sumDigits(int n) {
    if (n < 10) return n;                       // base case
    return n % 10 + sumDigits(n / 10);          // last digit + the rest
}

The important mental move is step 3: trust the smaller call. You do not trace what happens inside sumDigits(482) while writing the method. You assume it returns 14 and ask "given that, what is the answer for 4821?" The answer: 1 + 14. When you debug, you can trace; when you design, you trust.

Tracing: down, then up

Tracing sumDigits(4821) shows two phases on the call stack:

sumDigits(4821)  waits for  sumDigits(482)
  sumDigits(482)  waits for  sumDigits(48)
    sumDigits(48)  waits for  sumDigits(4)
      sumDigits(4)  returns 4          <- base case
    sumDigits(48)  returns 8 + 4 = 12
  sumDigits(482)  returns 2 + 12 = 14
sumDigits(4821)  returns 1 + 14 = 15

Going down, each call waits. At the base case the first answer appears. Going up, each waiting call finishes its own combine step. The result 15 is what my run printed.

Factorial and the missing base case

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

factorial(4) returned 24. Without a base case the method never stops:

static int broken(int n) { return n + broken(n - 1); }

Each call adds a new frame to the call stack and none returns. The JVM eventually throws StackOverflowError. In my run, try { broken(5); } catch (StackOverflowError e) { ... } caught it, and printed the name StackOverflowError. The Java API documentation describes this error as thrown when an application recurses too deeply. The exact depth at which it happens depends on the machine and settings, so do not rely on a particular number.

A base case that exists but is never reached has the same effect. For sumTo(n) with the base case if (n == 0), calling sumTo(-1) goes down forever, because n never equals 0. Writing n <= 0 is safer. The rule: every recursive call must move closer to the base case.

Order matters: before or after the call

Where you put the work changes the output. This code prints on the way down:

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

countdown(3) printed 3, 2, 1, Go!. If the print comes after the recursive call, it happens on the way up and the order reverses. A method with the print placed after countup(n - 1) printed 1, 2, 3 for countup(3). This idea (work before the call versus after) returns in the next lesson, where "undo" happens on the way back up.

Counting calls: simple versus halving

Consider power(b, e), "b to the power e":

static int power(int b, int e) {
    if (e == 0) return 1;
    return b * power(b, e - 1);   // e calls deep
}

For power(2, 10) the method makes 11 calls (e = 10 down to 0), so it takes about e steps: O(e).

A different smaller step: if e is even, b^e is (b^(e/2)) squared; if odd, one more factor of b.

static long fastPower(long b, int e) {
    if (e == 0) return 1;
    long half = fastPower(b, e / 2);
    return e % 2 == 0 ? half * half : half * half * b;
}

fastPower(2, 10) made only 5 calls (e = 10, 5, 2, 1, 0) and returned 1024, the same answer as power. Halving the problem each time takes about log₂(e) calls: O(log e). Notice we compute half once and reuse it; calling fastPower twice would lose the saving. A smaller step that cuts the problem by a fraction is far more powerful than one that cuts one item.

Recursion on text

Strings work well too: a palindrome reads the same in both directions.

1. Base case: a string of length 0 or 1 is a palindrome.
2. Smaller step: remove the first and last character (substring(1, length - 1)).
3. Combine: it is a palindrome only if the first and last characters match and the middle is a palindrome.

static boolean isPalindrome(String s) {
    if (s.length() < 2) return true;
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalindrome(s.substring(1, s.length() - 1));
}

Results: "level" true, "abca" false, "" true. Note that substring(begin, end) includes begin and excludes end, according to the Java API documentation.

Recursion or a loop?

Everything above could also be written with a loop. Prefer recursion when the problem is naturally nested (folders in folders, trees) or when branching creates many paths (the next lesson). Prefer a loop when the work is a simple repetition over a long range, because each recursive call uses stack space and a very deep recursion can overflow.