Counting Up and Counting Down

We are about to write merge sort recursively. You have seen recursion before, so most of this is review. But there is one idea about recursion that is easy to forget, and merge sort depends on it. So let’s go over it with two small methods.

In a recursive method, the work can happen at two different times. It can happen on the way down, as the calls go deeper. It can also happen on the way up, as the calls return. Which one you get depends on whether you put the work before or after the recursive call.

Counting down

Here is a method that prints the numbers from n down to 1:

public static void countDown(int n) {
  if (n == 0) {
    return;
  }
  System.out.println(n);
  countDown(n - 1);
}

Notice that the print comes before the recursive call. Let’s trace countDown(3):

countDown(3)
  print 3
  countDown(2)
    print 2
    countDown(1)
      print 1
      countDown(0)
        return

Each level prints its number and then calls the next level to print the rest. By the time we reach the base case, all the printing is already finished. Reading the prints from top to bottom, the output is:

3
2
1

The work happens on the way down.

Counting up

Now let’s make one change: swap the two lines so the recursive call comes first, and the print comes after.

public static void countUp(int n) {
  if (n == 0) {
    return;
  }
  countUp(n - 1);
  System.out.println(n);
}

Trace countUp(3):

countUp(3)
  countUp(2)
    countUp(1)
      countUp(0)
        return
      print 1
    print 2
  print 3

This time, countUp(3) reaches the base case without printing anything. Each level prints its number only as the calls return, one by one. The output is:

1
2
3

The work happens on the way up.

Carrying values in and out

As we go into a recursion and come back out of it, we can carry information in two directions:

• We carry information in, deeper into the recursion, through the parameters we pass to the recursive call.
• We carry information out, back toward the original caller, through the return value of the recursive call.

Here is a small example that does both. It adds up the numbers from 1 to n:

public static int sumTo(int n) {
  if (n == 0) {
    return 0;
  }
  int restSum = sumTo(n - 1);  // carry the smaller answer back up
  return restSum + n;          // combine it with our own piece, and hand it up
}

We carry n - 1 down as a parameter. The answer to the smaller problem comes back up as restSum. Then we add n to it and return the sum to the caller. That combining step is what merge sort is going to do.