Page 383 - Discrete Mathematics and Its Applications

362 5 / Induction and Recursion

EXAMPLE 3 Give a recursive algorithm for computing the greatest common divisor of two nonnegative
integers a and b with a< b.

Solution: We can base a recursive algorithm on the reduction gcd(a, b) = gcd(b mod a, a) and
the condition gcd(0,b) = b when b> 0. This produces the procedure in Algorithm 3, which is
a recursive version of the Euclidean algorithm.
We illustrate the workings of Algorithm 3 with a trace when the input is a = 5, b = 8. With
this input, the algorithm uses the “else” clause to find that gcd(5, 8) = gcd(8 mod 5, 5) =
gcd(3, 5). It uses this clause again to find that gcd(3, 5) = gcd(5 mod 3, 3) = gcd(2, 3), then
to get gcd(2, 3) = gcd(3 mod 2, 2) = gcd(1, 2), then to get gcd(1, 2) = gcd(2 mod 1, 1) =
gcd(0, 1). Finally, to find gcd(0, 1) it uses the first step with a = 0 to find that gcd(0, 1) = 1.
Consequently, the algorithm finds that gcd(5, 8) = 1. ▲

ALGORITHM 3 A Recursive Algorithm for Computing gcd(a, b).

procedure gcd(a, b: nonnegative integers with a< b)
if a = 0 then return b
else return gcd(b mod a, a)
{output is gcd(a, b)}

n
EXAMPLE 4 Devise a recursive algorithm for computing b mod m, where b, n, and m are integers with
m ≥ 2, n ≥ 0, and 1 ≤ b< m.
Solution: We can base a recursive algorithm on the fact that

n
b mod m = (b · (b n−1 mod m)) mod m,
0
which follows by Corollary 2 in Section 4.1, and the initial condition b mod m = 1. We leave
this as Exercise 12 for the reader.
However, we can devise a much more efficient recursive algorithm based on the observation
that

n n/2 2
b mod m = (b mod m) mod m

when n is even and

2
n

b mod m = (b n/2 mod m) mod m · b mod m mod m
when n is odd, which we describe in pseudocode as Algorithm 4.
We trace the execution of Algorithm 4 with input b = 2, n = 5, and m = 3 to illustrate how
it works. First, because n = 5 is odd we use the “else” clause to see that mpower(2, 5, 3) =
2
(mpower(2, 2, 3) mod 3 · 2 mod 3) mod 3. We next use the “else if” clause to see that
mpower(2, 2, 3) = mpower(2, 1, 3) 2 mod 3. Using the “else” clause again, we see that
2
mpower(2, 1, 3) = (mpower(2, 0, 3) mod 3 · 2 mod 3) mod 3. Finally, using the “if” clause,
we see that mpower(2, 0, 3) = 1. Working backwards, it follows that mpower(2, 1, 3) =
2
2
(1 mod 3 · 2 mod 3) mod 3 = 2, so mpower(2, 2, 3) = 2 mod 3 = 1, and finally
2
mpower(2, 5, 3) = (1 mod 3 · 2 mod 3) mod 3 = 2. ▲