The 3-Question Recipe

Don’t trace every call while you write code. Trust the smaller call. People call this the leap of faith.

The recipe

Answer these before you write any code:

static int sum(int n) {
    if (n == 0) return 0;          // base case
    return n + sum(n - 1);         // trust sum(n - 1), add n
}

Why can you trust it? If it works for the smallest input, and each step works whenever the smaller call works, then it works for every input. (This is mathematical induction.)

Try it: sum of digits

Ways to make the input smaller

Choosing the base case

1. Shrink the example until the answer is obvious (an empty array, n = 0).
2. Find where the step breaks. fib(n − 2) from n = 1 calls fib(−1), so both 0 and 1 need answers.
3. Check the guards first. Write if (i == a.length) before you read a[i].

What should a base case return? It depends on the question:

Return the answer, don’t carry it

There are two ways to build an answer:

// Return style: build it on the way back up
int sum(int[] a, int i) {
    if (i == a.length) return 0;
    return a[i] + sum(a, i + 1);
}

// Carry style: pass the total down
int sum(int[] a, int i, int soFar) {
    if (i == a.length) return soFar;
    return sum(a, i + 1, soFar + a[i]);
}

Use return style for counts, min, max and yes/no. Memo (chapter 3) only works when the answer depends only on the parameters. Carry style is fine for printing all paths.

Java detail: int values are copied into each call. Arrays and lists are shared: every call sees the same list. So undo your change after the call, and save a copy with new ArrayList<>(path).

Your turn

Do Trace the Output, then this chapter’s problems in order. Before coding each one, write the three answers as comments.