Recursion - Data Structures and Abstractions with Java - page 162

Question 3 Write a recursive void method countUp(n) that counts up from 1 to n , where n
is a positive integer. Hint : A recursive call will occur before you display anything.

Recursive Methods That Return a Value

7.11

The recursive method countDown in the previous sections is a void method. Valued methods can
also be recursive. The guidelines for successful recursion given in Segment 7.4 apply to valued
methods as well, with an additional note. Recall that a recursive method must contain a statement
such as an if that chooses among several cases. Some of these cases lead to a recursive call, but at
least one case has no recursive call. For a valued method, each of these cases must provide a value
for the method to return.

7.12

Example: Compute the sum 1 + 2 + . . . + n for any integer n > 0. The given input value for this
problem is the integer n . Beginning with this fact will help us to find the smaller problem because
its input will also be a single integer. The sum always starts at 1, so that can be assumed.
So suppose that I have given you a positive integer n and asked you to compute the sum of the
first n integers. You need to ask a friend to compute the sum of the first m integers for some positive
integer m . What should m be? Well, if your friend computes 1 + . . . + ( n - 1), you can simply add n
to that sum to get your sum. Thus, if sumOf(n) is the method call that returns the sum of the first n
integers, adding n to your friend's sum occurs in the expression sumOf(n-1) + n .
What small problem can be the base case? That is, what value of n results in a sum that you
know immediately? One possible answer is 1. If n is 1, the desired sum is 1.
With these thoughts in mind, we can write the following method:
/** @param n an integer > 0
@return the sum 1 + 2 + ... + n */
public static int sumOf( int n)
{

int sum;
if (n == 1)
sum = 1; // base case

else
sum = sumOf(n - 1) + n; // recursive call
return sum;
} // end sumOf

7.13

The definition of the method sumOf satisfies the design guidelines for successful recursion. There-
fore, you should be confident that the method will work correctly without tracing its execution.
However, a trace will be instructive here because it will not only show you how a valued recursive
method works, but also demonstrate actions that occur after a recursive call is complete.
Suppose that we invoke this method with the statement
System.out.println(sumOf(3));
The computation occurs as follows:

1. sumOf(3) is sumOf(2) + 3; sumOf(3) suspends execution, and sumOf(2) begins.
2. sumOf(2) is sumOf(1) + 2; sumOf(2) suspends execution, and sumOf(1) begins.
3. sumOf(1) returns 1.