Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 3] FUNCTIONS AND ALGORITHMS 53

And so on. Observe that

5 != 5 · 4 != 5 · 24 =120 and 6!= 6 · 5 != 6 · 120 = 720

This is true for every positive integern; that is,

n!=n·(n− 1 )!

Accordingly, the factorial function may also be defined as follows:

Definition 3.1 (Factorial Function):
(a) Ifn= 0 ,thenn!= 1.
(b) Ifn> 0 ,thenn!=n·(n− 1 )!

Observe that the above definition ofn! is recursive, since it refers to itself when it uses(n− 1 )!. However:

(1) The value ofn! is explicitly given whenn=0 (thus 0 is a base value).

(2) The value ofn!for arbitrarynis defined in terms of a smaller value ofnwhich is closer to the base

value 0.

Accordingly, the definition is not circular, or, in other words, the function is well-defined.

EXAMPLE 3.8 Figure 3-6 shows the nine steps to calculate 4! using the recursive definition. Specifically:

Step1.Thisdefines4!intermsof3!,sowemustpostponeevaluating4!untilweevaluate3.Thispostponement

is indicated by indenting the next step.

Step 2. Here 3! is defined in terms of 2!, so we must postpone evaluating 3! until we evaluate 2!.

Step 3. This defines 2! in terms of 1!.

Step 4. This defines 1! in terms of 0!.

Step 5. This step can explicitly evaluate 0!, since 0 is the base value of the recursive definition.

Steps 6 to 9. We backtrack, using 0! to find 1!, using 1! to find 2!, using 2! to find 3!, and finally using 3! to

find 4!. This backtracking is indicated by the “reverse” indention.

Observe that we backtrack in the reverse order of the original postponed evaluations.

Fig. 3-6