Programming and Problem Solving with Java

(^640) | Recursion
Because this is the last of the calls to factorial, the recur-
sive process ends. The value 24 is returned as the final value
of the call to factorialwith an argument of 4.
Figure 13.2 summarizes the execution of the factorial
method with an argument of 4.
Let’s organize what we have done in the preceding ex-
amples into an outline for writing recursive algorithms:

1. Understand the problem. (We threw this task in
   for good measure; it is always the first step.)


2. Determine the base case(s). A base case is one to
   which you know the answer. It does not involve
   any further recursion.


3. Determine the recursive case(s). A recursive case
   is one in which you can express the solution in
   terms of a smaller version of itself.

We have used the factorial and power algorithms to

demonstrate recursion because they are easy to visualize.

In practice, we would never want to calculate either of these

values using the recursive solution. That is, in both cases,

the iterative solutions are simpler and much more efficient

because starting a new iteration of a loop is a faster operation than calling a method. Let’s

compare the code for the iterative and recursive versions of the factorial problem.

Iterative Solution Recursive Solution

public static intfactorial(int number) public static intfactorial(int number )

{{

int factor;

int count;

factor = 1; if (number == 0)

for (count = 2; count <= number; count++) return1;

factor = factor * count; else

returnfactor; returnnumber * factorial(number – 1);

}}

The iterative version has two local variables, whereas the recursive version has none. A

recursive method usually includes fewer local variables than does an iterative method. Also,

the iterative version always has a loop, whereas the recursive version always has a selection

factorial( 4 )

Call 1:

Call 2:

Call 3:

Call 4:

Call 5:

Returns 24.

Returns 6.

Returns 2.

Returns 1.

Returns 1.

n 4 n 3 n 2 n 1 n 0

Figure 13.2 Execution of factorial( 4 )

T

E

A

M

F

L

Y

Team-Fly®