Java Reference
In-Depth Information
15.1.5
The recursive pattern
In the previous three subsections, three recursive methods were developed. They
follow a pattern that is shared by all recursive methods.
Activity
15-1.5
1. There is one (possibly more) base case . This is a case for which no recur-
sive calls are used; the desired result can be calculated without using
recursion. The case involves the “smallest” possible arguments. In
method setToZero , the base case was an empty array segment. In
method deblank , it was a string of length 0 . In method factorial , it was
an integer 0 .
2. There is one (possibly more) recursive case . This case requires a recur-
sive call. In method setToZero , the recursive case was a nonempty array
segment. In method deblank , it was a string with at least one character.
In method factorial , it was an integer that is greater than 0 .
In the recursive case, the idea is to identify a “smaller” problem of the same
type and write a recursive call for it. Thus, in developing the recursive case, we
look for a problem that has the same specification but on smaller values; this gen-
erally requires doing some processing before or after solving this smaller prob-
lem. This leads to recursive calls whose arguments are “smaller” than the param-
eters.
In method setToZero , the arguments of the recursive call were b,h+1,k .
In method deblank , the argument was p[1..] . And in method factorial , the
argument was n-1 .
How are the arguments of the recursive calls smaller? In method setToZero ,
the size of segment b[h + 1..k] is one less than the size of b[h..k] . In method
deblank , the length of p[1..] is one less than the length of parameter p . And in
method factorial , n-1 is smaller than n .
The big idea
Developing a recursive method will follow naturally as long as you hold
consciously to the idea that in the recursive case, you have to:
Recursion strategy . Identify a problem that is the same as the
specification of the method but on a smaller scale.
/** = n! (assuming n≥0 ) */
public static int factorial( int n) {
if (n == 0)
{ return 1; }
// { n > 0 }
return n * factorial(n - 1);
}
Figure 15.3:
Recursive function factorial

Search WWH ::

Custom Search