Expert: Zlatko - 6/5/2011

Question
QUESTION: The following is recursive pseudocode:

Function expo2(a, n)
 if n = 1 then
   return a

 if n is even then
   return (expo2(a, n ÷2))2
 else
   return a * expo2(a, n-1)

-----------------------------
The following is iterative pseudocode of
Function expo2(a, n):

function expo2(a, n)
 i= n
 result = 1
 x = a
 while i> 0 do
 if i is odd then
 result = result * x
 x = x * x
 i= i÷2
 return result
-----------------------------
Pls let me know whether the iterative pseudocode is correct?

ANSWER: Edit:
In the second program, the line while (reached * 2 < n)
should read
while (reached * 2 <= n)

Hi James.

I am sorry for the late response. I don't think the two versions are the same. Notice the first version has a part where the exponent n is decremented by one, but the second version does not have anything like that. To use the idea of squaring a result until the exponent is reached, you could do something like this:

long exp(int a, int n)
{
   if (n == 0) return 1;

   int reached = 1;
   int result = a;
   while (reached * 2 < n)
   {
       result = result * result;
       reached *= 2;
   }
   while(reached < n)
   {
       result = result * a;
       ++reached;
   }

   return result;
}
The first while loop multiplies result by itself, and doubles the exponent reached, as long as the doubling the exponent reached does not go past the desired exponent n.
So, to calculate n^17, it calculates result = n^2, then multiplies the result by itself to get n^4, then again to get n^16. Doing the loop again would result in n^32, which is too large, so the routine moves to the second loop part and increments the reached exponent by one until it matches the desired exponent n.

This is not a direct translation of the recursive code, and in fact it is less efficient than the recursive code. To have a proper translation from recursive to iterative you need some kind of array to hold partial results. The array takes the place of the stack in the recursive version. (Note, in tail recursion, you don't need a stack, but this is not tail recursion). Here is my translation. Note that I have no error checking for stack overflow.

long exp(int a, int n)
{
   if (n == 0) return 1;
   
   int prevResult[64]; // this array replaces the stack
   int prevIx = 0; // this is an index into the stack

   int result = a;

   while (n > 1)
   {
       // reached represents the exponent reached
       int reached = 1;
       result = a;
       while (reached * 2 <= n)
       {
         result = result * result;
         reached *= 2;
       }
       // place the partial result on the stack, and
       // go back to calculate a new partial result
       // with a new n
       prevResult[prevIx++] = result;
       n = n - reached;
   }

   // now multiply out all the partial results
   if (n == 0) result = 1;
   else result = a;
   while(--prevIx >= 0)
   {
       result *= prevResult[prevIx];
   }
   return result;
}

---------- FOLLOW-UP ----------

QUESTION: Hi

I was thinking what will be the iterative version for this:

Function expo2(a, n)
if n = 1 then
  return a

if n is even then
  return (expo2(a, n/2))2
else
  return a * expo2(a, n-1)


----
How do I derive from recursive algo to iterative algo?

Answer
Hello James.
Sorry, I don't have an algorithm for turning a recursive solution to an iterative one. In general, look at the exit condition of the recursion. That will be translated to some sort of loop condition. So where you have the recursion exit condition "if n = 1 then return a" you will have a while loop which stops when n is 1 in the iterative solution.

After that you need to think about the calculations being done and put them into the loop. In the recursive solution, we have the idea of multiplying a partial result by itself, to reduce the number of calculations. That is in the line "return (expo2(a, n/2))2" It allows us to cut an exponent in half instead of just reducing it by 1. We would need to do something similar in the iterative solution.

The recursive solution keeps calling itself with smaller and smaller n until n is 1, and then the result starts building up as the stack unwinds. In the iterative solution, we would not do this. We would use a loop to start building up the results right away. So,instead of cutting n in half, we would multiply a partial result by itself and double some variable representing the current exponent of the partial result.

In doing the transformation, you will need more variables to keep track information which might have been hidden on the stack in the recursive solution. The transformation will be more than just a rearrangement of lines and the transformation will not use the same ideas  as the original recursion. For example, checking if n is even or odd is not part of the iterative solution.

Now, I'd like to go back to the code, because I think it may help you. As I think about it more, we don't need a stack array in the iterative solution, although in some cases, as stack array is necessary. We just need to have a finalResult variable and a partialResult variable. Once a partialResult is known, it can be multiplied into the finalResult. Here is my solution. Sorry that I cannot explain it better. I think you should get other people's opinion for this question.

double exp(double a, int n)
{
   if (n == 0) return 1;
   
   double finalResult = 1;

   while (n > 1)
   {
       // reached represents the exponent reached
       int reached = 1;
       double partialResult = a;
       while (reached * 2 <= n)
       {
         partialResult = partialResult * partialResult;
         reached *= 2;
       }
       finalResult *= partialResult;
       n -= reached;
   }

   if (n == 1)
   {
       finalResult *= a;
   }
   return finalResult;
}