Implementation of Variable Layer Loops and a Generalized Method for Recursive to Non-Recursive Conversion

2023-08-16T18:23:00

Problem

平常我们最多只写 3 重循环，比如：

for (let i = 0; i < 3; i++)
  for (let j = 0; j < 3; j++)
    for (let k = 0; k < 3; k++)
      console.log(i, j, k);

以上代码输出如下：

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

每层循环对应一条 for 语句，这种硬编码方式无法应对循环层数可变的情况。备用解决方案是动态生成源码文本，创建编译或解释器进程执行，但这肯定不是我们想要的。

Approach 1

针对这个具体问题，可以发现虽然循环层数不定，但每层循环执行的次数是固定的，并且以上输出就是 3 进制数从 0 自增。因此，可预先求出总循环次数，每次令最低位（最内层下标）加一，不断往前进位。

/**
 * @param {[[number, number]]} bound 整数对数组，包含 n 个元素，
 *  第 i 个元素为数对数组 [l, r]，表示第 i 层循环下标从 l 开始，
 *  到 r 结束
 */
function loop(bound) {
  let tot = 1;
  for (const [l, r] of bound)
    tot *= r - l + 1;
  
  const n = bound.length;
  const indice = bound.map(([l]) => l);
  while (tot--) {
    console.log(indice.join(' '));
    indice[n - 1]++;
    for (let i = n - 1; i >= 0; i--) {
      const [l, r] = bound[i];
      if (indice[i] > r) {
        indice[i] = l;
        // 冗余判断，可去除
        if (i >= 1)
          indice[i - 1]++;
      }
    }
  }
}

loop([
  [0, 2],
  [0, 2],
  [0, 2]
]);

以上代码输出同文章开头的 3 重循环。

Approach 2

除了逐个进位，可直接根据公式得到每层循环变量的下标，大体思路为，每层下标都在相应的 [l, r] 内循环，当前层循环变量的下标等于内部所有层执行的周期数。具体来说，若当前执行到第 i 次输出，最内层下标为 i 模上最内层周期，倒数第二层下标为 i 除以最内层周期再模上本层周期，倒数第三层下标为 i 除以最内层周期乘以倒数第二层周期再模上本层周期，以此类推。

/**
 * @param {[[number, number]]} bound 整数对数组，包含 n 个元素，
 *  第 i 个元素为数对数组 [l, r]，表示第 i 层循环下标从 l 开始，
 *  到 r 结束
 */
function loop(bound) {
  const circle = [];
  const circleSuffixProduct = [];
  const n = bound.length;
  for (let i = n - 1; i >= 0; i--) {
    const [l, r] = bound[i];
    circleSuffixProduct[i] = circle[i] = r - l + 1;
    if (i + 1 < n)
      circleSuffixProduct[i] *= circleSuffixProduct[i + 1];
  }
  
  const indice = [];
  for (let i = 0; i < circleSuffixProduct[0]; i++) {
    for (let j = 0; j < n; j++) {
      indice[j] = i;
      if (j + 1 < n)
        indice[j] = Math.floor(i / circleSuffixProduct[j + 1]);
      indice[j] %= circle[j];
      indice[j] += bound[j][0];
    }
    console.log(indice.join(' '));
  }
}

loop([
  [0, 2],
  [0, 2],
  [0, 2]
]);

Recursion Approach

其实，以上逻辑用递归很容易实现，每层递归对应一层循环，到第 n 层停止。

/**
 * @param {number} u 当前执行第 u 层循环
 * @param {[[number, number]]} bound 整数对数组，包含 n 个元素，
 *  第 i 个元素为数对数组 [l, r]，表示第 i 层循环下标从 l 开始，
 *  到 r 结束
 * @param {[number]} indice 保存一轮 n 层循环的所有下标
 */
function loop(u, bound, indice) {
  if (u == bound.length) {
    console.log(indice.join(' '));
    return;
  }
  
  const [l, r] = bound[u];
  for (let i = l; i <= r; i++) {
    indice[u] = i;
    loop(u + 1, bound, indice);
  }
}

loop(
  0,
  [
    [0, 2],
    [0, 2],
    [0, 2]
  ],
  []
);

Recursion to Iteration

递归实现不仅简单，而且能处理内层下标依赖外层的情况，下面以打印全排列为例，首先给出递归实现，再将其转为非递归，并由此总结递归转迭代的通用方法。

const used = [];
const path = [];

/**
 * 打印 1 ~ n 的全排列
 * 
 * @param {number} u 当前填充第 u 个数
 * @param {number} n 打印到 n 结束
 */
function dfs(u, n) {
  if (u == n) {
    console.log(path.join(' '));
    return;
  }
  
  for (let i = 1; i <= n; i++) {
    if (!used[i]) {
      used[i] = true;
      path[u] = i;
      dfs(u + 1, n);
      used[i] = false;
    }
  }
}

dfs(0, 3);

以上代码输出如下：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Principle

递归仍是函数调用，每调用一个函数，编译或解释器便会将函数参数、局部变量和下一条指令地址压入系统栈，返回时再将栈顶弹出恢复上一级函数执行现场，以上过程可手动模拟。大体步骤如下：

定义函数调用栈，用于保存每一层函数调用的参数、局部变量和下一条语句分支号。

class Stack {
  constructor() {
    this.memory = [];
    this.sp = -1;
  }

  push(frame) {
    this.memory[++this.sp] = frame;
  }

  pop() {
    --this.sp;
  }

  top() {
    return this.memory[this.sp];
  }

  empty() {
    return this.sp == -1;
  }
}

// 单功能系统
class OS {
  // 堆，全局变量区
  static heap = {
    n,
    used: [],
    path: [],
  };

  // 栈，局部变量区，包括函数参数
  static stack = new Stack();

  static fun = {
    // 函数调用，将局部变量压栈
    call: (u) =>
      OS.stack.push({
        pc: 0,
        u,
        i: 0,
      }),
    // 函数返回，弹出栈帧
    ret: () => OS.stack.pop(),
  };
}

将递归函数拆分成 switch 块，遇到 if, for, while, return、函数调用等非顺序执行流，或需要回溯恢复现场，就增加一个 case 分支 。将递归出口放在第一个分支，初始化放在第二个分支，返回放在最后一个分支，为回溯保留单独分支。break 总是跟在 pc 改变后。将第一层函数调用现场压栈，若栈不空，重复执行以下步骤：取栈顶恢复执行现场，根据 pc 值跳转相应 case 执行。

// 初始调用
OS.fun.call(0);
while (!OS.stack.empty()) {
  const { n, used, path } = OS.heap;
  const frame = OS.stack.top();
  switch (frame.pc) {
    case 0:
      // 递归出口
      if (frame.u == n) {
        console.log(path.join(" "));
        frame.pc = 5;
        break;
      }
      frame.pc = 1;
      break;
    case 1:
      // 循环初始化
      frame.i = 1;
      frame.pc = 2;
      break;
    case 2:
      // 循环条件
      if (frame.i > n) {
        frame.pc = 5;
        break;
      }
      // 循环体
      if (!used[frame.i]) {
        used[frame.i] = true;
        path[frame.u] = frame.i;
        OS.fun.call(frame.u + 1);
        frame.pc = 3;
        break;
      }
      frame.pc = 4;
      break;
    case 3:
      // 回溯恢复调用者全局变量
      used[frame.i] = false;
      frame.pc = 4;
      break;
    case 4:
      // 循环递增
      frame.i++;
      frame.pc = 2;
      break;
    case 5:
      // 函数返回
      OS.fun.ret();
      break;
  }
}

改造后的完整代码如下：

/**
 * 打印 1 ~ n 的全排列
 *
 * @param {number} n 打印到 n 结束
 */
function permutation(n) {
  class Stack {
    constructor() {
      this.memory = [];
      this.sp = -1;
    }

    push(frame) {
      this.memory[++this.sp] = frame;
    }

    top() {
      return this.memory[this.sp];
    }

    pop() {
      --this.sp;
    }

    empty() {
      return this.sp == -1;
    }
  }

  class OS {
    static heap = {
      n,
      used: [],
      path: [],
    };

    static stack = new Stack();

    static fun = {
      call: (u) =>
        OS.stack.push({
          pc: 0,
          u,
          i: 0,
        }),
      ret: () => OS.stack.pop(),
    };
  }

  OS.fun.call(0);
  while (!OS.stack.empty()) {
    const { n, used, path } = OS.heap;
    const frame = OS.stack.top();
    switch (frame.pc) {
      case 0:
        if (frame.u == n) {
          console.log(path.join(" "));
          frame.pc = 5;
          break;
        }
        frame.pc = 1;
        break;
      case 1:
        frame.i = 1;
        frame.pc = 2;
        break;
      case 2:
        if (frame.i > n) {
          frame.pc = 5;
          break;
        }
        if (!used[frame.i]) {
          used[frame.i] = true;
          path[frame.u] = frame.i;
          OS.fun.call(frame.u + 1);
          frame.pc = 3;
          break;
        }
        frame.pc = 4;
        break;
      case 3:
        used[frame.i] = false;
        frame.pc = 4;
        break;
      case 4:
        frame.i++;
        frame.pc = 2;
        break;
      case 5:
        OS.fun.ret();
        break;
    }
  }
}

permutation(4);

Supplement

如果函数有返回值，也一并放到栈上，参数、返回值都属于局部变量，放到栈或寄存器都可以。具体操作是，弹出栈帧后，修改当前栈帧返回值。

Summary

递归转循环有固定的步骤，可操作性适中，但转换后的代码变长，逻辑被打散，可阅读性下降，运行效率也未必变高，仅用于理解函数调用原理。

References

当前页面是本站的「Baidu MIP」版。发表评论请点击：完整版 »

© 2024 MIP for Typecho v0.8 , Designed by Holmesian.