如何在JavaScript中将自底向上的递归算法转换为迭代堆栈

机械地将任何递归代码转换为堆栈计算机并非易事。自动状态转换会产生非常复杂的代码，只需要考虑C＃或BabelJS的生成器即可。但是可以肯定的是，可以做到，但是您将需要可变的堆栈帧和/或寄存器。让我们看看我们面临的问题：

机器如何记住在哪里继续执行功能？

我们必须在堆栈本身上存储一些状态变量/指令指针。这就是您使用

"open"

"close"

函数结果放在哪里？

有很多方法：

• 将其存储在临时寄存器中
• 将函数的引用传递给字段（（对象，字段名称）对），并模拟

  out

  参数
• 使用像@CtheSky这样的第二个堆栈

使用可变堆栈帧和结果寄存器，转换后的代码将如下所示：

console.log(JSON.stringify(create(0), null, 2))function Klass(i, l, r) {  this.i = i  this.l = l  this.r = r}function frame(i) {  this.ip = 0;  this.i = i;  this.left = null;}function create(i) {  var result;  var stack = [new frame(i)];  while (stack.length > 0) {    var frame = stack[stack.length - 1];    switch (frame.ip) {      case 0:        if (frame.i === 5) {          result = undefined;          stack.pop();          break;        }        stack.push(new frame(frame.i + 1));        frame.ip = 1;        break;      case 1:        frame.left = result;        stack.push(new frame(frame.i + 1));        frame.ip = 2;        break;      case 2:        result = new Klass(frame.i, frame.left, result);        stack.pop();        break;    }  }  return result;}