java如何将递归转换为迭代？

Question

这个问题被问了几次，但我仍然发现很难将易读且直观的代码转换为迭代代码。例如，我在练习一个编码问题，我得到了26个整数，表示每个字符在字符串中出现的次数。我应该打印所有可能的字符串。下面是我的递归代码

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);
        }
    }
}

我编写了这个迭代版本，但生成的函数要复杂得多，不可读，而且我花了更多的时间来编写它。我如何解决这类问题？有没有什么简单的技术可以让我遵循，从而产生简单易读的代码

Answer 1

编程语言支持程序的递归表达式的原因是它通常比显式迭代形式简单。所以你的问题几乎是自我回答

然而，确实有一种方法可以将递归形式转换为总是有效的迭代形式。有一种带有goto的语言是有帮助的，而Java没有

首先，让我们清理java。我们希望使用最少数量的参数和局部变量，因为剩下的必须放在显式堆栈上。我们开始吧。除了i和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("");
  }
}

现在让我们转录到C，它有goto。在这里，通过添加一个全局字符串缓冲区，很容易消除甚至prefix

#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];
    }
  }
}

现在，规则是：

• 构建一个记录堆栈，每个局部变量和参数有一个字段。这里我们只剩下i，所以我们甚至不需要记录。一堆int就可以了
• 将递归调用站点替换为
  • 将push放在堆栈上，然后
  • 将参数重置为新值（这里没有），然后
  • 跳转到函数的开头，然后
  • 跳转之后，立即放置一个标签rtn:
• 在函数的末尾，添加一个epilog来检查堆栈是否为空。如果没有，它将弹出堆栈并跳到rtn:

这些规则基本上模仿编译器将生成的代码来处理递归调用

综上所述，我们有：

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;
  }
}

如果您仔细遵循这些步骤，您的代码将首先运行，然后每次尝试。唯一的额外提示是，当存在多个递归调用站点时，您需要为每个rtn1:、rtn2:等添加一个返回标签，并在堆栈中添加一个表示返回站点的int字段，在epilog中使用switch语句跳转到正确的返回站点

当然这不是很好的代码。我们想去掉goto。通过做“代数”将gotos转换成循环，这总是可能的。有几十种转换技术。。。太多了，这里无法描述。这很像在数学课上简化方程式。有时需要添加布尔标志。不过，在这种情况下，我们不需要这样做。我完成了这个：

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;
  }
}

为了好玩，回到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;
    }
  }
}

Answer 2

public static void combinatorial(ArrayList<Integer> remainingToFill, int totalLength) {
    Stack st = new Stack();
    st.push( new Pair<String,Integer>("", 0) );
    while( !st.empty() ){
        Pair<String,Integer> top = (Pair<String,Integer>) st.pop();
        String prefix = top.getKey();
        Integer i = top.getValue();
        if (prefix.length() == totalLength) {
            System.out.println(prefix);
            int index= prefix.charAt(prefix.length()-1 )-'a' ;
            remainingToFill.set( index , remainingToFill.get(index) + 1 );
        }
        else{
            if( i== remainingToFill.size() ){
                if( prefix.length()>0 ){
                    int index= prefix.charAt(prefix.length()-1 )-'a' ;
                    remainingToFill.set( index , remainingToFill.get(index) + 1 );
                }
            }
            else{
                st.push( new Pair<String,Integer>(prefix, i+1) );
                if( remainingToFill.get(i) > 0 ){
                    remainingToFill.set(i, remainingToFill.get(i) - 1);
                    st.push( new Pair<String,Integer>(prefix+(char)('a'+i), 0) );
                }
            }
        }
    }
}