Page 384 - Discrete Mathematics and Its Applications

5.4 Recursive Algorithms 363

ALGORITHM 4 Recursive Modular Exponentiation.

procedure mpower(b, n, m: integers with b> 0 and m ≥ 2, n ≥ 0)
if n = 0 then
return 1
else if n is even then
2
return mpower(b, n/2,m) mod m
else
2
return (mpower(b, n/2 ,m) mod m · b mod m) mod m
n
{output is b mod m}

We will now give recursive versions of searching algorithms that were introduced in Section 3.1.

EXAMPLE 5 Express the linear search algorithm as a recursive procedure.

Solution: To search for the first occurrence of x in the sequence a 1 , a 2 ,...,a n ,atthe ith step of
the algorithm, x and a i are compared. If x equals a i , then the algorithm returns i, the location
of x in the sequence. Otherwise, the search for the first occurrence of x is reduced to a search in
a sequence with one fewer element, namely, the sequence a i+1 ,...,a n . The algorithm returns
0 when x is never found in the sequence after all terms have been examined. We can now give
a recursive procedure, which is displayed as pseudocode in Algorithm 5.
Let search (i,j,x) be the procedure that searches for the first occurrence of x in the sequence
a i ,a i+1 ,..., a j . The input to the procedure consists of the triple (1,n,x). The algorithm
terminates at a step if the first term of the remaining sequence is x or if there is only one term of
the sequence and this is not x.If x is not the first term and there are additional terms, the same
procedure is carried out but with a search sequence of one fewer term, obtained by deleting the
first term of the search sequence. If the algorithm terminates without x having been found, the
algorithm returns the value 0. ▲

ALGORITHM 5 A Recursive Linear Search Algorithm.

procedure search(i,j,x: i, j, x integers, 1 ≤ i ≤ j ≤ n)
if a i = x then
return i
else if i = j then
return 0
else
return search(i + 1,j,x)
{output is the location of x in a 1 ,a 2 ,...,a n if it appears; otherwise it is 0}

EXAMPLE 6 Construct a recursive version of a binary search algorithm.

Solution: Suppose we want to locate x in the sequence a 1 , a 2 ,...,a n of integers in increasing
order. To perform a binary search, we begin by comparing x with the middle term, a (n+1)/2 .
Our algorithm will terminate if x equals this term and return the location of this term in the
sequence. Otherwise, we reduce the search to a smaller search sequence, namely, the first half
of the sequence if x is smaller than the middle term of the original sequence, and the second
half otherwise. We have reduced the solution of the search problem to the solution of the same