Friday, October 24, 2008

pow(n, m) would never terminate for m > 0

The following code was shown in today's lecture as one of the alternatives to single-call recursion on pow(n, m):

0. def pow(n, m)
1. if m == 0: return 1
2. else: return pow(n, Floor(m / 2)) * pow(n, Ceiling(m / 2))


Since we used floors and ceilings, I take it that m is an integer. Then for an m > 0, a call to pow(n, m) would execute line 2. But Ceiling(m / 2) will never be 0 for an integer m > 0, so line 2 would get executed indefinitely on pow(n, Ceiling(m / 2)'s recursive call, causing the program to never terminate.

I think that adding "else if m == 1: return n" before the last else branch would fix this problem.

No comments: