Recursion - Data Structures and Problem Solving Using Java - page 298

1 // Evaluate the sum of the first n integers
2 public static long s( int n )
3 {
4 if( n == 1 )
5 return 1;
6 else
7 return s( n - 1 ) + n;
8 }

figure 7.1
Recursive evaluation
of the sum of the first
N integers

Sometimes writing a formula recursively is easier than writing it in closed
form. Figure 7.1 shows a straightforward implementation of the recursive function.
If N = 1, we have the basis, for which we know that S (1) = 1. We take care of this
case at lines 4 and 5. Otherwise, we follow the recursive definition S ( N ) = S ( N - 1)
+ N precisely at line 7. It is hard to imagine that we could implement the recursive
method any more simply than this, so the natural question is, does it actually work?
The answer, except as noted shortly, is that this routine works. Let us
examine how the call to s(4) is evaluated. When the call to s(4) is made, the
test at line 4 fails. We then execute line 7, where we evaluate s(3) . Like any
other method, this evaluation requires a call to s . In that call we get to line 4,
where the test fails; thus we go to line 7. At this point we call s(2) . Again, we
call s , and now n is 2. The test at line 4 still fails, so we call s(1) at line 7. Now
we have n equal to 1, so s(1) returns 1. At this point s(2) can continue, adding
the return value from s(1) to 2; thus s(2) returns 3. Now s(3) continues, add-
ing the value of 3 returned by s(2) to n , which is 3; thus s(3) returns 6. This
result enables completion of the call to s(4) , which finally returns 10.
Note that, although s seems to be calling itself, in reality it is calling a
clone of itself. That clone is simply another method with different parameters.
At any instant only one clone is active; the rest are pending. It is the com-
puter's job, not yours, to handle all the bookkeeping. If there were too much
bookkeeping even for the computer, then it would be time to worry. We dis-
cuss these details later in the chapter.

A base case is an instance that can be solved without recursion. Any
recursive call must progress toward the base case in order to terminate eventu-
ally. We thus have our first two (of four) fundamental rules of recursion.
1. Base case: Always have at least one case that can be solved without
using recursion.
2. Make progress: Any recursive call must progress toward a base case.
Our recursive evaluation routine does have a few problems. One is the call
s(0) , for which the method behaves poorly. 1 This behavior is natural because

The base case is an
instance that can
be solved without
recursion. Any
recursive call must
make progress
toward a base case.

1. A call to s(-1) is made, and the program eventually crashes because there are too many
pending recursive calls. The recursive calls are not progressing toward a base case.