How to convert recursion to iteration? [closed]

Question

This question is asked few times but I still find it quite difficult to convert easily readable and intuitive code into iterative code. For example I was practicing a coding question and I am given 26 integers which indicate how many times each character appears in the string. I should print all possible strings. Following is my recursive code

private static void combinatorial(String prefix, ArrayList<Integer> remainingToFill,
        int totalLength) {
    if (prefix.length() == totalLength) {
        System.out.println(prefix);
    }
    for (int i = 0; i < remainingToFill.size(); i++) {
        if (remainingToFill.get(i) > 0) {
            ArrayList<Integer> toFill = new ArrayList<>(remainingToFill);
            toFill.set(i, toFill.get(i) - 1);
            combinatorial(prefix + (char) ('a' + i), toFill, totalLength);
        }
    }
}

I coded iterative version of this but the resultant function is much more complex and not readable and took more time for me to code it. How do I tackle this kind of problem? Is there any simple technique I can follow which would lead to easy and readable code?

Answer 1

Well, the reason programming languages support recursive expression of programs is that it's often simpler than explicit iterative forms. So your question is almost self-answering.

However, there really is a methodical way to convert recursive forms to iterative forms that always works. It helps to have a language with goto, which Java doesn't.

First let's clean up the java. We want to use a minimum number of arguments and local variables because what's left must go on our explicit stack. Here we go. We do away with all except i and prefix.

class CombinationLister {
  private final int[] counts;
  private final int length;

  CombinationLister(int[] counts) {
    this.counts = counts.clone();
    this.length = Arrays.stream(counts).sum();
  }

  private void list(String prefix) {
    if (prefix.length() == length) {
      System.out.println(prefix);
    }
    for (int i = 0; i < counts.length; i++) {
      if (counts[i] > 0) {
        --counts[i];
        list(prefix + (char) ('a' + i));
        ++counts[i];
      }
    }
  }

  void run() {
    list("");
  }
}

Now let's transcribe to C, which has goto. Here it's easy to eliminate even prefix by adding a global string buffer.

#include <stdio.h>

char str[100];
int counts[] = { 1, 2, 3 };
int n_counts = 3;
int total_count = 6;
int len = 0;

void list(void) {
  if (len == total_count) printf("%.*s\n", total_count, str);
  for (int i = 0; i < n_counts; i++) {
    if (counts[i] > 0) {
      str[len] = 'a' + i;
      --counts[i];
      ++len;
      list();
      --len;
      ++counts[i];
    }
  }
}

Now, the rules are:

• Build a stack of records with one field for each local variable and parameter. Here we have only i left, so we don't even need records. A stack of ints will do.
• Replace the recursive call site with
  • a push onto the stack, then
  • reset the parameters to their new values (here we don't have any), then
  • jump to the start of the function, and
  • immediately after the jump, put a label rtn:.
• At the end of the function, add an epilog that checks whether the stack is empty. If not, it pops the stack and jumps to rtn:.

These rules essentially mimic the code the compiler will generate to handle recursive calls.

Putting it all together, we have:

int stk[100];
int p = 0; // stack pointer

void list(void) {
  int i;
 start:
  if (len == total_count) printf("%.*s\n", total_count, str);
  for (i = 0; i < n_counts; i++) {
    if (counts[i] > 0) {
      str[len] = 'a' + i;
      --counts[i];
      ++len;
      stk[p++] = i;  // push i on stack
      goto start;
     rtn:
      --len;
      ++counts[i];
    }
  }
  // epilog
  if (p > 0) {
    i = stk[--p];  // restore i from stack
    goto rtn;
  }
}

If you follow the steps carefully, your code will run first try every time. The only additional tip is that when there is more than one recursive call site, you'll need one return label for each rtn1:, rtn2:, etc. and an extra int field in the stack that connotes the return site, with a switch statement in the epilog to jump to the correct one.

Of course this isn't pretty code. We'd like to get rid of the gotos. It turns out this is always possible by doing "algebra" to convert the gotos to loops. There are a couple of dozen transformation techniques...too many to describe here. It's a lot like simplifying an equation in math class. Sometimes it's necessary to add Boolean flags. In this case, though, we don't need to. I finished with this:

void list(void) {
  for (int i = 0;;) {
    while (i < n_counts && counts[i] == 0) i++;
    if (i < n_counts) {
      --counts[i];
      str[len] = 'a' + i;
      stk[p++] = i;
      if (++len == total_count) printf("%.*s\n", total_count, str);
      i = 0;
    } else if (p > 0) {
      i = stk[--p];
      --len;
      ++counts[i++];
    }
    else break;
  }
}

Just for fun, back to Java:

class CombinationLister {
  private final int[] counts;
  private final char[] str;
  private final int[] stk;
  private int p = 0;
  private int len = 0;

  CombinationLister(int[] counts) {
    this.counts = counts.clone();
    this.str = new char[Arrays.stream(counts).sum()];
    this.stk = new int[str.length];
  }

  void run() {
    for (int i = 0;;) {
      while (i < counts.length && counts[i] == 0) i++;
      if (i < counts.length) {
        --counts[i];
        str[len] = (char) ('a' + i);
        stk[p++] = i;
        if (++len == str.length) System.out.println(str);
        i = 0;
      } else if (p > 0) {
        i = stk[--p];
        --len;
        ++counts[i++];
      } else break;
    }
  }
}