What is the best way to convert a recursive function to an iterative?

Question

This question is based on a test I conducted in the 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 non-recursive, but I am struggling with it because System.out.print(number % 2) happens after a recursive call.

Answer 1

You can always simulate a stack, of course, but in many cases you can convert it to a completely levelless solution. (I'm not 100% sure, but I think that conversion without a stack is only possible for primitive recursive functions . I don't see anything like this . Ackermann function can be computed without any stack.)

In any case, in most cases in practice (and in all cases in the classroom) you can find a way. Here we can use the oncoming trick:

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

Update: The easiest way to convert simple functions is to run it, write the result after each iteration, then completely forget about recursion, forget about the source code, look at the result yourself and ask yourself: what does this code do? Then just try writing iterative code that produces the same result. This technique served me well. However, this does not always work in real life. :)

Answer 2

Just for a different look at the problem, since you already have a lot of answers.

It is true that a cover-based approach for solving recursion is to use a stack. However, if you know exactly what you decide, you can find an alternative solution. Or maybe not an alternative for sure - only one that will be more compact.

In this case, the function gives a 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, can only earn points for courage in the test.

So here is an adaptation of how 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)); } } 

This is actually using the stack, but not very complicated. A stack is just an array of characters that you start filling from the end, and go to the beginning. You can use such an array instead of a collection, because it is known that an int contains no more than 32 bits. This way you will never encounter the boundaries of an array. In truth, because you only work with positive numbers, it could even be a 31-character array.

So, in each case, you put the current digit in the current empty position in the array and move the pointer to the left. As a result, you convert all the characters that you have collected into a string using the String constructor, which, as convenient, can use the specified part of the character array.

The actual statements used by Java are slightly different:

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

since shift and camouflage are more efficient operations than division. If you use this version, it is just as effective as when using Integer.toBinaryString() .

Answer 3

You can use Deque to track 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 } } 

Answer 4

Perhaps prepending for the string?

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

Answer 5

The best way to simulate recursion is with the stack and use push and pop, as recursion works this way:

 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 6

The general approach to recursion-exception is to replicate how the compiler performs recursion using Stack . This approach can be applied to transform any recursive program into a non-recursive one.

We use Stack to store various stack frames corresponding to each recursive call. Each frame of the stack must somehow track its position during code execution. The better we distinguish between these stack frames (i.e., the main execution steps), the easier our decision will be.

For your recursive function, each stack stack can be divided into two main parts of execution:

---

A) check if number is > 0 and call foo pass number / 2 as an argument

B) type 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, 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 nep used to store the next position during program execution for each StackFrame .

The program will process executable parts A and B :

A) The program uses the Stack from StackFrames and pushes a new StackFrame each time it replicates a recursive call, and the condition number > 0 is true. (This will be the base case in your recursion)

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

Here's what this approach looks like:

 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 the complete sample program

Example output for number = 211 :

 Recursive output: 11010011 Iterative output: 11010011 

Here are some great visual examples for eliminating recursion