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

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. :)