Previous Section
 < Free Open Study > 
Next Section


7.2 The Classic Example of Recursion

Mathematicians often define concepts in terms of the process used to generate them. For instance, n! (read "n factorial") is used to calculate the number of permutations of n elements. One mathematical description of n! is

Consider the case of 4!. Because n > 0, we use the second part of the definition:

4! = 4*3*2*1 =24

This description of n! provides a different definition for each value of n, as the three dots stand in for the intermediate factors. That is, the definition of 2! is 2 * 1, the definition of 3! is 3 * 2 * 1, and so forth.

We can also express n! with a single definition for any nonnegative value of n:

This definition is a recursive definition, because we express the factorial function in terms of itself.

Recursive definition A definition in which something is defined in terms of a smaller version of itself

Let's consider the recursive calculation of 4! intuitively. Because 4 is not equal to 0, we use the second half of the definition:

4! = 4*(4- 1)! = 4*3!

Of course, we can't do the multiplication yet, because we don't know the value of 3!. So we call up our good friend Sue Ann, who has a Ph.D. in math, to find the value of 3!.

Click To expand

Sue Ann has the same formula we have for calculating the factorial function, so she knows that

3! = 3*(3 - 1)! = 3*2!

She doesn't know the value of 2!, however, so she puts us on hold and calls up her friend Max, who has an M.S. in math.

Click To expand

Max has the same formula Sue Ann has, so he quickly calculates that

2! = 2*(2 - 1)! = 2*1!

But Max can't complete the multiplication because he doesn't know the value of 1! He puts Sue Ann on hold and calls up his mother, who has a B.A. in math education.

Click To expand

Max's mother has the same formula Max has, so she quickly figures out that

1! = 1 *{1 - 1)!=1 * 0!

Of course, she can't perform the multiplication, because she doesn't have the value of 0!. So Mom puts Max on hold and calls up her colleague Bernie, who has a B.A. in English literature.

Click To expand

Bernie doesn't need to know any math to figure out that 0! = 1 because he can read that information in the first clause of the formula (n! = 1, if n = 0). He reports the answer immediately to Max's mother. She can now complete her calculations:

1! = 1 "0!= 1 * 1 = 1

She reports back to Max, who now performs the multiplication in his formula and learns that

2! = 2 * 1! = 2 * 1 = 2

He reports back to Sue Ann, who can now finish her calculation:

Click To expand

3! = 3 * 2! = 3 * 2 = 6

Sue Ann calls you with this exciting bit of information. You can now complete your calculation:

4! = 4 * 3! = 4 * 6 = 24

Notice when the recursive calls stop-when we reach a case for which we know the answer without resorting to a recursive definition. In this example, Bernie knew that 0! = 1 directly from the definition without having to resort to recursion. The case (or cases) for which an answer is explicitly known is called the base case. The case for which the solution is expressed in terms of a smaller version of itself is called the recursive or general case. A recursive algorithm expresses the solution in terms of a call to itself-that is, a recursive call. A recursive algorithm must terminate; that is, it must have a base case.

Base case The case for which the solution can be stated nonrecursively

General (recursive) case The case for which the solution is expressed in terms of a smaller version of itself

Recursive algorithm A solution that is expressed in terms of (1) smaller instances of itself and (2) a base case



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)