RECURSION - Java Programming: From Problem Analysis to Program Design - page 877

example, if method A calls method B and method B calls method A , then method A is
indirectly recursive. Indirect recursion could be several layers deep. For example, if
method A calls method B , method B calls method C , method C calls method D , and
method D calls method A , then method A is indirectly recursive.
Indirect recursion requires the same careful analysis as direct recursion. The base cases
must be identified and nonrecursive solutions to them must be provided. However,
tracing through indirect recursion can be a tedious process. Therefore, extra care must be
exercised when designing indirect recursive methods. For simplicity, this topic considers
only problems that involve direct recursion.
A recursive method in which the last statement executed is the recursive call is called a
tail recursive method. The method fact is an example of a tail recursive method.

Infinite Recursion
Figure 13-1 shows that the sequence of recursive calls reached a call that made no further
recursive calls. That is, the sequence of recursive calls eventually reached a base case.
However, if every recursive call results in another recursive call, then the recursive
method (algorithm) is said to have infinite recursion. In theory, infinite recursion
executes forever. However, every call to a recursive method requires the system to
allocate memory for the local variables and formal parameters. In addition, the system
also saves the information so that after completing a call, control can be transferred back
to the caller. Therefore, because computer memory is finite, if you execute an infinite
recursive method on a computer, the method will execute until the system runs out of
memory, which results in an abnormal termination of the program.

Designing Recursive Methods
Recursive methods (algorithms) must be designed and analyzed carefully. You must make
sure that every recursive call eventually reduces to a base case. The following sections
give various examples illustrating how to design and implement recursive algorithms.
To design a recursive method, you must:
1. Understand the problem requirements.
2. Determine the limiting conditions. For example, for a list, the limiting
condition is determined by the number of elements in the list.
3. Identify the base cases and provide a direct (nonrecursive) solution to
each base case.
4. Identify the general cases and provide a solution to each general case in
terms of a smaller version of itself.
Typically, all recursive methods have the following characteristics: (a) they use an
if...else or a switch statement that leads to different cases, (b) one or more base
cases are used to stop recursion, and (c) each recursive call reduces the problem to a
smaller version of itself.

1
3