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

The base case of this definition is 1!, which is defined as 1. All other
values of N ! (for N > 1) are defined recursively as N times the value
( N −1)!. The recursion is that the factorial function is defined in
terms of the factorial function.
Using this definition, 50! is equal to 50 * 49!. And 49! is equal to 49 * 48!.
And 48! is equal to 48 * 47!. This process continues until we get to the base case
of 1. Because N ! is defined only for positive integers, this definition is complete
and will always conclude with the base case.
The next section describes how recursion is accomplished in programs.

KEY CONCEPT
Mathematical problems and formulas
are often expressed recursively.

SELF-REVIEW QUESTIONS (see answers in Appendix N)
SR 12.1 What is recursion?
SR 12.2 How many times is the recursive part of the definition of a List used
to define a list of 10 numbers? How many times is the base case used?
SR 12.3 What is infinite recursion?
SR 12.4 When is a base case needed for recursive processing?
SR 12.5 Write a recursive definition of 5 * n (integer multiplication), where
n > 0. Define the multiplication process in terms of integer addition.
For example, 5 * 7 is equal to 5 added to itself 7 times.

12.2 Recursive Programming

Let's use a simple mathematical operation to demonstrate the concept of recur-
sive programming. Consider the process of summing the values between 1 and N
inclusive, where N is any positive integer. The sum of the values from 1 to N can
be expressed as N plus the sum of the values from 1 to N −1. That sum can be
expressed similarly, as shown in Figure 12.2.

N N -1 N -2

∑ ∑ ∑

= N + = N + +

N - 1

i i i

i = 1 i = 1 i = 1

N -3

∑

= + + +

i

N N - 1 N - 2

.

i = 1

= + + + + +

N N - 1 N - 2 2 1

FIGURE 12.2 The sum of the numbers 1 through N , defined recursively