17.8. Tracing Calls Across Two Methods¶

Problem: How can we compute the sum of the sums from zero through a small nonnegative integer n? For example, when n is 2, we want (0) + (0 + 1) + (0 + 1 + 2), which is 4.

Let's break this into two methods. First, sum(n) should compute the sum of the integers from zero through n. Then, sumOfSums(n) can combine sum(n) with the sum of the sums through n - 1. Use small nonnegative inputs so that the results fit in an int and the calls do not exhaust the call stack.

Given the above problem description, identify the base case for each method. Now, try to write both methods.

Don't read beyond this point until you've attempted to write the two recursive methods.

Sample Solution

Both methods are included in the cs1302-recursion bundle on the Recursive String Reversal page:

public static int sum(int n) {
    if (n == 0) {
        return 0;
    } // if
    return n + sum(n - 1);
} // sum

public static int sumOfSums(int n) {
    if (n == 0) {
        return 0;
    } // if
    return sum(n) + sumOfSums(n - 1);
} // sumOfSums

Notice that sumOfSums calls both sum and itself. This is not mutual recursion: sum never calls sumOfSums. Each method makes progress toward its own base case.

Sample Recursion Tree

Here is a sample recursion tree for sumOfSums(2):

sumOfSums(2)
|-- sum(2)
|   `-- sum(1)
|       `-- sum(0)
`-- sumOfSums(1)
    |-- sum(1)
    |   `-- sum(0)
    `-- sumOfSums(0)

Java evaluates the left operand of + before the right operand. Therefore, the call sum(n) must complete normally before evaluation can proceed to sumOfSums(n - 1). The two branches of the tree are not executed at the same time.

Starting with sumOfSums(2), the method calls begin in this order:

sumOfSums(2), sum(2), sum(1), sum(0),
sumOfSums(1), sum(1), sum(0), sumOfSums(0)

As the calls complete normally, sum(2) supplies 3, sumOfSums(1) supplies 1, and the original call combines them to produce 4. Inside sumOfSums(1), the result is 1 + 0.

Sample Call Stack

The list above records all of the calls, not the contents of the stack at one moment. Immediately after the first call to sum(0), the active example-method frames are, from oldest to newest:

sumOfSums(2)    waiting for sum(2), then sumOfSums(1)
sum(2)         waiting to add 2 to sum(1)
sum(1)         waiting to add 1 to sum(0)
sum(0)         ready to supply 0

There are four frames here. After sum(0), sum(1), and sum(2) complete, only the original sumOfSums(2) frame remains from this list. The next call is sumOfSums(1). Its call to sum(1) also reaches a depth of four example-method frames, but those are different method calls from the ones shown above.

The maximum depth for this example is four, counting only active calls to sum and sumOfSums. We are not counting the driver or library methods. Eight calls begin over the whole computation; they are never all on the stack at once.

Test Yourself

Which method call begins immediately after the first sum(0) call completes? Be careful to distinguish beginning a new call from resuming a call that is already on the stack.
If we swapped the operands in the recursive case of sumOfSums, would the call-entry order stay the same? Would the result for sumOfSums(2) stay the same?