Consider computing ( bn mod m). There is a non-recursive version to compute this
ID: 3721657 • Letter: C
Question
Consider computing ( bn 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.
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
Explanation / Answer
Lets first find the comparison between Iteration and Recursion based on some questions.
Q: Is the recursive version usually faster?
A: No -- it's usually slower (due to the overhead of maintaining the stack)
Q: Does the recursive version usually use less memory?
A: No -- it usually uses more memory (for the stack).
Q: Then why use recursion??
A: Sometimes it is much simpler to write the recursive version. It is very useful in certain tress algorithm implementation.
In this case also, the iterative approach is better than recursion. Because, recusrion uses a LIFO stack to persist the function calls.As a result, recursive methods ends up taking extra space than non-recursive method.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.