Revisiting Recursion

We have used recursion in several earlier chapters. Here is a recursive method that computes the factorial of n:

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

It has the two parts from the sorted-array chapter. The if is the base case: the method returns 1 without making a recursive call. The return below it is the recursive case: it assumes that factorial(n - 1) already gives the right answer for the smaller problem, and multiplies that answer by n.

That assumption is what recursion depends on. We do not trace factorial(n - 1) all the way down in our heads. We ask only one question: given that answer, how do I build the answer for n?

Every recursive method we have written fits this two-part shape:

• Binary search. The base case is an empty range (the value is not there). The recursive case searches one half of the range.
• Merge sort. The base case is a range of length zero or one, which is already sorted. The recursive case sorts each half, then merges the two sorted halves.
• Maze search. The base case is reaching the exit (solved), or hitting a wall, the edge, or a cell already visited. The recursive case tries to solve the maze from a neighboring cell.

These methods share that shape, but they differ in how many recursive calls they make. Factorial makes one. Merge sort makes two. The maze search can make up to four.