Recursion - Data Structures and Abstractions with Java - page 180

Making these changes results in the following revised algorithm:
Algorithm solveTowers(numberOfDisks, startPole, tempPole, endPole)
while (numberOfDisks > 0)
{

solveTowers(numberOfDisks - 1, startPole, endPole, tempPole)
Move disk from startPole to endPole
numberOfDisks--
Exchange the contents of tempPole and startPole

}

This revised algorithm is unusual in that its loop contains a recursive call. The base case for
this recursion occurs when numberOfDisks is zero. Even though the method does not contain an if
statement, it does detect the base case, ending the recursive calls.

Note: In a tail-recursive method, the last action is a recursive call. This call performs a rep-
etition that can be done by using iteration. Converting a tail-recursive method to an iterative
one is usually a straightforward process.

Indirect Recursion

7.44

Some recursive algorithms make their recursive calls indirectly. For example, we might have the
following chain of events: Method A calls Method B, Method B calls Method C, and Method C
calls Method A. Such recursion—called indirect recursion —is more difficult to understand and
trace, but it does arise naturally in certain applications.
For example, the following rules describe strings that are valid algebraic expressions:

•

An algebraic expression is either a term or two terms separated by a + or - operator.

• A term is either a factor or two factors separated by a * or / operator.

•

A factor is either a variable or an algebraic expression enclosed in parentheses.

•

A variable is a single letter.

Suppose that the methods isExpression , isTerm , isFactor , and isVariable detect whether a
string is, respectively, an expression, a term, a factor, or a variable. The method isExpression calls
isTerm , which in turn calls isFactor , which then calls isVariable and isExpression . Figure 7-11
illustrates these calls.
A special case of indirect recursion, where Method A calls Method B, and Method B calls Method A,
is called mutual recursion . Project 10 at the end of this chapter describes an example of mutual recursion.

FIGURE 7-11

An example of indirect recursion

isExpression isTerm

isFactor

isExpression isTerm isFactor

isExpression isTerm isFactor isVariable