Recursion - Multimedia Introduction to Programming Using Java - page 395

In order to eliminate the phrase “series of” from this definition, we give a
two-part recursive definition . A noun phrase is either:

a noun

1.

or

an adjective followed by a noun phrase.

2.

We use this definition to construct noun phrases. Since dog is a noun, part 1
of the definition tells us that dog is a noun phrase. Since loud is an adjective, part
2 then tells us that loud dog is a noun phrase. Since big is an adjective, part 2 tells
us that big loud dog is a noun phrase.
The definition of noun phrase is recursive because it is defined in terms of
itself: part 2 of the definition uses noun phrase to help define noun phrase .
Such recursive definitions occur often throughout mathematics and fields
that use mathematics —for example, linguistics, which attempts (among other
things) to define grammars for natural languages like English.

15.1.2 A recursive procedure

We develop a procedure that sets the elements in a segment of an array to 0 :
/** Set elements of b[h..k] to 0. Precondition: h<=k+1*/
public static void setToZero( int [] b, int h, int k)
In writing the method body, we consider two cases: the segment is empty and it
is not empty. If the segment is empty, there are no elements to be set to 0 , so the
method body can be terminated using a return statement. Second, if b[h..k] is
nonempty, then first element, b[h] , can be set to 0 . Thereafter, the rest of the ele-
ments of the segment have to be set to 0 . We indicate this in the method body
with an English statement. The body, shown below, is correct, except that it con-
tains an English statement.

Activity
15-1.2

See lesson
page 15.1 to
get the proce-
dure from the
CD.

if (h == k + 1)
{ return ; }
// { b[h..k] is nonempty }
b[h]= 0;
Set elements of b[h + 1..k] to 0 // English statement
We implement the English statement. It has the same form as the procedure
spec, except that it has expression h+1 instead of parameter h . Therefore, the
English statement can be implemented by a recursive call to this method:

setToZero(b, h + 1, k);
It is called a recursive call because it appears in the body of the method that it is
calling. The final procedure is in Fig. 15.1.