How do you best convert a recursive function to an iterative one?

Question

This question is based on a test I had in a compsci class. In particular, I'm struggling to convert this function:

public static void foo(int number)  {
    if (number > 0) {
        foo(number / 2);
        System.out.print(number % 2);
    }
}

I need to convert this function to be non-recursive, but I'm struggling with it because the System.out.print(number % 2) occurs after the recursive call.

Answer 1

A generic approach to recursion-elimination is to replicate how the compiler performs recursion by using a Stack. This approach can be applied to convert any recursive program into a non-recursive.

The way we use a Stack is to store different stack frames corresponding to each recursive call. Each stack frame needs to somehow keep track of its position during code execution. The better we distinguish these stackframes (i.e. main execution steps), the simpler our solution will get.

For your recursive function, each stack frame can be split into two main execution parts:

---

A) check if number is > 0 and call foo passing number / 2 as the argument

B) print number % 2

---

Or in the code:

// all marked A are a single "step"
public static void foo(int number)  {
    if (number > 0) {                   //   A  
        foo(number / 2);                //   A 
        System.out.print(number % 2);   //   B
    }
}

So let's create a StackFrame class that will replicate this:

static class StackFrame {
    int number;
    char nep;   // Next Execution Position ('A' or 'B')
    StackFrame(int number, char nep) {
        this.number = number;
        this.nep = nep;
    }
}

The nep variable is used to store the next position in the execution of the program for each StackFrame.

The program will treat execution parts A and B:

A) Program uses a Stack of StackFrames and pushes a new StackFrame each time it is replicating a recursive call and while condition number > 0 is true. (This would be the base case in your recursion)

B) Once this condition (base case) is reached, we can start popping StackFrames of the stack the same way compiler does and print our desired value (number % 2).

Here is how this approach would look:

public static void iterative(int number) {
    Stack<StackFrame> stack = new Stack<StackFrame>();
    stack.push(new StackFrame(number, 'A'));
    while(!stack.isEmpty()) {  // run until we have stack frames
        StackFrame top = stack.peek();
        switch(top.nep) { // determine next execution step
        case 'A':
            top.nep = 'B'; // set next execution step
            if(top.number / 2 > 0) { // check base case and push current stack frame if base case is true
                stack.push(new StackFrame(top.number / 2, 'A'));
            }
            break;
        case 'B':
            System.out.print(top.number % 2);
            stack.pop();    // end current stack frame 
            break;
        }
    }
}

Here is a full sample program

Sample program output for number = 211:

Recursive output:   11010011
Iterative output:   11010011

Here are some great visual examples for recursion elimination

Answer 2

Just for another perspective on the issue, since you already have plenty of answers.

It's true that the cover-all approach to solve a recursion is to use a stack. However, if you know what you are solving exactly, you can find an alternative solution. Or maybe not alternative exactly - just one that will be more compact.

In this instance, the function gives you the binary representation of the parameter, for integers greater than zero.

You may be tempted to use:

   public static void foo(int number) {

       if ( number > 0 ) {
           System.out.print( Integer.toBinaryString(number) );
       }

   }

But this, of course, may only earn you points for audacity in a test.

So here is an adaptation of the way Java actually does this:

public static void foo(int number) {

    if (number > 0) {
        char[] chars = new char[32];
        int charPos = 32;
        char[] digits = { '0', '1' };

        do {
            chars[--charPos] = digits[number % 2];
            number /= 2;
        } while (number > 0);

        System.out.print(new String(chars, charPos, 32 - charPos));
    }
}

It is, in fact, using a stack, but not a very complicated one. The stack is merely an array of chars which you start filling from the end, and go towards the start. You can use such an array instead of a Collection, because it is a known fact that an int contains no more than 32 bits. So you will not ever run out of the bounds of the array. Truth be told, because you are only working with positive numbers, it can even be a 31-character array.

So in each turn you place the current digit in the current empty position in the array, and move the index to the left. In the end you convert all the characters you collected into a string by using a constructor of String which, conveniently, can use a specified part of a character array.

The actual operators used by Java are a bit different:

        do {
            chars[charPos--] = digits[number & 1];
            number >>>= 1;
        } while (number != 0);

because shifting and masking are more efficient operations than divison. If you use this version, it's as efficient as using Integer.toBinaryString().

Answer 3

You can always simulate the stack of course but in a lot of cases you can convert it to a completely stackless solution. (I'm not 100% sure but I think the stack-free conversion is only possible for primitive recursive functions. I can see no way something like the Ackermann function can be computed without some sort of stack.)

Anyway, for most cases in practice (and all cases in the class room) it is possible to find a way. Here we can use the counter trick:

public static void foo(int number)  {
    for ( int divisor = 1; divisor <= number; divisor *= 2) {
      System.out.print( (number / divisor) % 2 );
    }
}

Update: The easiest practical way to convert simple functions like this is to run it, write down the output after each iteration, then forget about recursion completely, forget about the original code, look at the output alone and ask yourself: what is this code doing? Then just try to write iterative code that produces the same output. This technique served me well at uni. It doesn't always work in real life though. :)

Answer 4

the best way to mimic recursion its by using a stack, and using push and pop, since that is how recursion works:

public static void foo2(int number)
{ 
    Stack st = new Stack();
   for(int i=number;i>0;i=i/2)
   {
       st.push(i%2);
   }
   while(!st.empty())
   {
       System.out.print(st.pop());
   }
}

Answer 5

Perhaps prepending to a String?

public static void foo(int number) {
    String r = "";
    while(number > 0) {
        r = (number%2)+r;
        number = number/2;  
    }
    System.out.print(r);
}

Answer 6

You could use a Deque to keep track of what you need to print

public static void foo(int number)  {
    Deque<Integer> stack = new ArrayDeque<Integer>();
    while (number > 0) {
        stack.push(number);
        number = number/2;
    }
    //iterate over the stack...
    while(!stack.isEmpty()){ 
        Integer myInt = stack.pop();
         //your code here
    }
}