4.16 - Recursion

A recursive method is a method that calls itself. Every recursive method needs at least one base case (a condition that stops the recursion) and at least one recursive call. Recursion is really just another way of doing repetition.

Each time a recursive call happens, it gets its own independent set of local variables and parameters. The parameter values basically track the progress of the recursive process, kind of like how a loop control variable tracks progress in a regular loop.

Note: writing your own recursive code is outside the scope of this course, you just need to be able to trace through recursive code and figure out what it returns.


// Example to trace through (not something you'll be asked to write from scratch)
public int factorial(int n) {
    if (n == 0) {          // base case
        return 1;
    }
    return n * factorial(n - 1); // recursive call
}

Here’s how factorial(4) runs. Each call pauses and waits for the call it made to return:


factorial(4) = 4 * factorial(3)
  factorial(3) = 3 * factorial(2)
    factorial(2) = 2 * factorial(1)
      factorial(1) = 1 * factorial(0)
        factorial(0) = 1                  base case, the recursion stops

Now each paused call finishes, from the bottom up:
      factorial(1) = 1 * 1 = 1
    factorial(2) = 2 * 1 = 2
  factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

Each of those five calls has its own n. While factorial(1) is running with n equal to 1, the factorial(4) call is still paused with its own n equal to 4. That’s how each call can finish its own multiplication once the answer comes back.

If a method never reaches its base case (calling factorial(-1) goes to -2, -3, and so on, never reaching 0), the calls pile up until Java runs out of room for them and throws a StackOverflowError.

When a recursive method prints, check whether the print comes before or after the recursive call:


public void countDown(int n) {
    if (n > 0) { // base case: when n is 0, do nothing
        System.out.print(n + " ");
        countDown(n - 1);
    }
}

public void countUp(int n) {
    if (n > 0) { // base case: when n is 0, do nothing
        countUp(n - 1);
        System.out.print(n + " ");
    }
}

// countDown(3) prints 3 2 1
// countUp(3) prints 1 2 3

In countDown, each call prints first, then makes the next call. In countUp, each call makes the next call first and only prints after that call is completely done, so the prints happen on the way back up, starting with the deepest call.

Any recursive solution has an equivalent iterative version, and vice versa, they can always be rewritten in terms of each other.

For example, this loop gives the same answers as the recursive factorial above. The loop control variable i does the job that the parameter n did in the recursive version:


public int factorialLoop(int n) {
    int result = 1;
    for (int i = n; i > 0; i--) {
        result *= i;
    }
    return result;
}

Back Next