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

一尘不染

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

algorithm

给定以下算法：

console.log(JSON.stringify(create(0), null, 2))



function create(i) {

  if (i == 5) return

  return new Klass(i, create(i + 1), create(i + 1))

}



function Klass(i, l, r) {

  this.i = i

  this.l = l

  this.r = r

}

它Klass在递归创建所有子代之后创建in create(0) last 。因此，它首先创建叶节点，然后将其传递给父节点，依此类推。

想知道如何使用没有递归的堆栈来做到这一点。使我的头受伤:)。我了解如何使用堆栈从上至下而不是自下而上进行创建。对于自顶向下，本质上是这样的：

var stack = [0]
while (stack.length) {
  var i = stack.pop()
  // do work
  stack.push(children)
}

从下至上，我看不到它应该如何工作。这是我卡住的地方：

function create(i) {  
  var stack = []
  stack.push([i, 'open'])
  stack.push([i, 'close'])

  while (stack.length) {
    var node = stack.pop()
    if (node[1] == 'open') {
      stack.push([ node[0] + 1, 'open' ])
      stack.push([ node[0] + 1, 'close' ])
    } else {
      // ?? not sure how to get to this point
      var klass = new Klass(node[0], node[2], node[3])
      // ??
    }
  }
}

阅读 281

2020-07-28

共1个答案

一尘不染

机械地将任何递归代码转换为堆栈计算机并非易事。自动状态转换会产生非常复杂的代码，只需要考虑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;

}

2020-07-28