Page 382 - Discrete Mathematics and Its Applications

5.4 Recursive Algorithms 361

DEFINITION 1 An algorithm is called recursive if it solves a problem by reducing it to an instance of the
same problem with smaller input.

We will describe a variety of different recursive algorithms in this section.

EXAMPLE 1 Give a recursive algorithm for computing n!, where n is a nonnegative integer.
Solution: We can build a recursive algorithm that finds n!, where n is a nonnegative integer,
based on the recursive definition of n!, which specifies that n!= n · (n − 1)! when n is a positive
integer, and that 0!= 1. To find n! for a particular integer, we use the recursive step n times,
each time replacing a value of the factorial function with the value of the factorial function at
the next smaller integer. At this last step, we insert the value of 0!. The recursive algorithm we
obtain is displayed as Algorithm 1.
To help understand how this algorithm works, we trace the steps used by the algorithm
to compute 4!. First, we use the recursive step to write 4!= 4 · 3!. We then use the recursive
step repeatedly to write 3!= 3 · 2!,2!= 2 · 1!, and 1!= 1 · 0!. Inserting the value of 0!= 1,
and working back through the steps, we see that 1!= 1 · 1 = 1, 2!= 2 · 1!= 2, 3!= 3 · 2!=
3 · 2 = 6, and 4!= 4 · 3!= 4 · 6 = 24. ▲

ALGORITHM 1 A Recursive Algorithm for Computing n!.

procedure factorial(n: nonnegative integer)
if n = 0 then return 1
else return n · factorial(n − 1)
{output is n!}

Example 2 shows how a recursive algorithm can be constructed to evaluate a function from its
recursive definition.
n
EXAMPLE 2 Give a recursive algorithm for computing a , where a is a nonzero real number and n is a
nonnegative integer.

n
Solution: We can base a recursive algorithm on the recursive definition of a . This definition
n
n
0
states that a n+1 = a · a for n> 0 and the initial condition a = 1. To find a , successively
use the recursive step to reduce the exponent until it becomes zero. We give this procedure in
Algorithm 2. ▲
n
ALGORITHM 2 A Recursive Algorithm for Computing a .

procedure power(a: nonzero real number, n: nonnegative integer)
if n = 0 then return 1
else return a · power(a, n − 1)
n
{output is a }

Next we give a recursive algorithm for finding greatest common divisors.