如何将递归转换为迭代？

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下了,所以我们甚至不需要记录.一堆ints会做.
• 用,替换递归调用站点
  • 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在张三返回现场堆栈场,与所述出口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;
    }
  }
}