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

In previous chapters, we used the common technique called iteration to devise problem
solutions. For certain problems, however, using the iterative technique to obtain the
solution is quite complicated. This chapter introduces another problem-solving technique
called recursion and provides several examples demonstrating how recursion works.
Recursive Definitions
The process of solving a problem by reducing it to successively smaller versions of itself is
called recursion. Recursion is a powerful way to solve certain problems for which the
solution can otherwise be very complicated. Let's consider a familiar problem.
In mathematics, the factorial of a nonnegative integer is defined as follows:
0! ¼ 1 ð 13-1 Þ
n! ¼ n ð n 1 Þ ! if n > 0 ð 13-2 Þ
In this definition, 0! is defined to be 1, and if n is an integer greater than 0, first we
find (n 1)! and then multiply it by n. To find (n 1)!, we apply the definition again. If
(n 1) > 0, we use Equation 13-2; otherwise, we use Equation 13-1. Thus, for an
integer n greater than 0, n! is obtained by first finding (n 1)! (that is, n! is determined in
part by a smaller, but similar problem) and then multiplying (n 1)! by n.
Let's apply this definition to find 3!. Here, n ¼ 3. Because n > 0, we use Equation 13-2 to
obtain:
3! ¼ 3 2!
Next we find 2!. Here, n ¼ 2. Because n > 0, we use Equation 13-2 to obtain:
2! ¼ 2 1!
Now, to find 1!, we again use Equation 13-2 because n ¼ 1 > 0. Thus:
1! ¼ 1 0!
Finally, we use Equation 13-1 to find 0!, which is 1. Substituting 0! into 1! gives 1! ¼ 1.
This gives 2! ¼ 2 1! ¼ 2 1 ¼ 2, which in turn gives 3! ¼ 3 2! ¼ 3 2 ¼ 6.
Note that the solution in Equation 13-1 is direct—that is, the right side of the equation
contains no factorial notation. The solution in Equation 13-2 is given in terms of a
smaller version of itself. The definition of the factorial as given in Equations 13-1 and
13-2 is called a recursive definition. Equation 13-1 is called the base case, the case for
which the solution is obtained directly; Equation 13-2 is called the general case or
recursive case.