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