Page 386 - Discrete Mathematics and Its Applications

5.4 Recursive Algorithms 365

INDUCTIVE STEP: For the inductive hypothesis we assume that mpower(b,j,m) =
j
b mod m for all integers 0 ≤ j< k whenever b is a positive integer and m is an integer with
m ≥ 2. To complete the inductive step, we show that if the inductive hypothesis is correct, then
k
mpower(b,k,m) = b mod m. Because the recursive algorithm handles odd and even values
of k differently, we split the inductive step into two cases.
When k is even, we have

2
2
k
mpower(b,k,m) = (mpower(b, k/2, m)) mod m = (b k/2 mod m) mod m = b mod m,
where we have used the inductive hypothesis to replace mpower(b, k/2,m) by b k/2 mod m.
When k is odd, we have
2
mpower(b,k,m) = ((mpower(b, k/2 , m)) mod m · b mod m) mod m
2
= ((b k/2 mod m) mod m · b mod m) mod m
k
= b 2 k/2 +1 mod m = b mod m,
using Corollary 2 in Section 4.1, because 2 k/2 + 1 = 2(k − 1)/2 + 1 = k when k is odd.
Here we have used the inductive hypothesis to replace mpower(b, k/2 ,m) by b k/2 mod m.
This completes the inductive step.
We have completed the basis step and the inductive step, so by strong induction we know
that Algorithm 4 is correct. ▲

Recursion and Iteration

A recursive definition expresses the value of a function at a positive integer in terms of the
values of the function at smaller integers. This means that we can devise a recursive algorithm to
evaluate a recursively defined function at a positive integer. Instead of successively reducing the
computation to the evaluation of the function at smaller integers, we can start with the value of the
function at one or more integers, the base cases, and successively apply the recursive definition to
find the values of the function at successive larger integers. Such a procedure is called iterative.
Often an iterative approach for the evaluation of a recursively defined sequence requires much
less computation than a procedure using recursion (unless special-purpose recursive machines
are used).This is illustrated by the iterative and recursive procedures for finding thenth Fibonacci
number. The recursive procedure is given first.

ALGORITHM 7 A Recursive Algorithm for Fibonacci Numbers.

procedure fibonacci(n: nonnegative integer)
if n = 0 then return 0
else if n = 1 then return 1
else return fibonacci(n − 1) + fibonacci(n − 2)
{output is fibonacci(n)}

When we use a recursive procedure to find f n , we first express f n as f n−1 + f n−2 . Then we
replace both of these Fibonacci numbers by the sum of two previous Fibonacci numbers, and
so on. When f 1 or f 0 arises, it is replaced by its value.
Note that at each stage of the recursion, until f 1 or f 0 is obtained, the number of Fibonacci
numbers to be evaluated has doubled. For instance, when we find f 4 using this recursive algo-
rithm, we must carry out all the computations illustrated in the tree diagram in Figure 1. This