Recursion - Java Software Solutions: Foundations of Program Design - page 585

LIST: number comma LIST

24 , 88, 40, 37

number comma LIST

88 , 40, 37

number comma LIST

40 , 37

number

37

FIGURE 12.1 Tracing the recursive definition of List

case. If all options had a recursive component, the recursion would
never end. For example, if the definition of

KEY CONCEPT
Any recursive definition must have
a non-recursive part, called the base
case, which permits the recursion to
eventually end.

List was simply “a num-
ber followed by a comma followed by a List ,” no list could ever end.
This problem is called infinite recursion. It is similar to an infinite

loop except that the “loop” occurs in the definition itself.
As in the infinite loop problem, a programmer must be careful to
design algorithms so that they avoid infinite recursion. Any recursive definition
must have a base case that does not result in a recursive option. The base case of
the List definition is a single number that is not followed by anything. In other
words, when the last number in the list is reached, the base case option terminates
the recursive path.

Recursion in Math
Let's look at an example of recursion in mathematics. The value referred to as N !
(pronounced N factorial ) is defined for any positive integer N as the product of
all integers between 1 and N inclusive. Therefore, 3! is defined as:

3! = 3*2*1 = 6

and 5! is defined as:

5! = 5*4*3*2*1 = 120.

Mathematical formulas are often expressed recursively. The definition of N !
can be expressed recursively as:

1! = 1
N! = N * (N-1)! for N > 1