Chapter 5 - Recursion

Question 1

To demonstrate the mechanics of recursion, we
begin with a simple mathematical
example of computing the value of the [f…al f…on]. The factorial of a positive
integer n, denoted n!, is defined as the product of the
of the integers from 1 to n. If
n = 0, then n! is defined as 1 by convention.

Answer 1

factorial function 191

Question 2

For example, 5! = 5 ·4 ·3 ·2 ·1 = 120. The factorial function is important because
it is known to equal the number of ways in which n distinct items can be arranged
into a sequence, that is, the number of [pe..s] of n items. For example, the
three characters a, b, and c can be arranged in 3! = 3 · 2 · 1 = 6 ways: abc, acb,
bac, bca, cab, and cba.

Answer 2

permutations 191

Question 3

More generally, for a positive integer n,
we can define n! to be n ·(n−1)!. This [re..e d..n] can be formalized as
n! =
#
1 if n = 0
n ·(n−1)! if n ≥ 1.

Answer 3

recursive definition 191

Question 4

This definition is typical of many recursive definitions of functions. First, we
have one or more b…se c..es, which refer to fixed values of the function. The above
definition has one base case stating that n! = 1 for n = 0. Second, we have one
or more [r..ve c..es], which define the function in terms of itself. In the above
definition, there is one recursive case, which indicates that n!=n(1)! for n≥1.

Answer 4

base cases, recursive cases 191

Question 5

We illustrate the execution of a recursive method using a [re…n t..e]. Each
entry of the trace corresponds to a recursive call. Each new recursive method call
is indicated by a downward arrow to a new invocation.

Answer 5

recursion trace 192