Consider computing ( b^n mod m). There is a non-recursive version to compute this function. The pseudocode for the function me below using computes this value using a modular exponentiation technique. (See the discussion starting on page Rosen on pg 253)

procedure me (b: integer,

n = (ak-1 ak-2 a1 a0) 2 ,

m: positive integer)

x = 1

power = b mod m

for I = 0 to k -1

if ai = 1 then x = ( x*power) mod m

power = (power*power) mod m

return x

This may also be expressed recursively as

procedure me (b: integer, n: integer m: integer) // with b>0 and m ?2, n ?0

if n = 0 then

return 1

else if n is even

return me(b, n/2, m)2 mod m

else

return (me(b ,floor( n/2), m)2 mod m * b mod m) mod m

Explain the benefits of expressing and implementing the algorithm recursively. Be sure to quantify your answer. Give an example to illustrate any potential savings or costs of the recursive approaches.