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

2022-01-24 00:00:00 递归 algorithm iteration javascript

给定以下算法:

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
}

它在create(0) last中创建Klass，递归地创建所有的孩子.所以它首先创建叶节点，然后将其传递给父节点，等等.

It creates the Klass in create(0) last, after creating all the children, recursively. So it creates the leaf nodes first, then passes that up to the parent, etc.

想知道如何使用没有递归的堆栈来做到这一点.让我头疼:).我了解如何使用堆栈从自上而下创建，而不是自下而上.对于自上而下，本质上是这样的:

Wondering how to do this using a stack without recursion. Making my head hurt :). I understand how to use a stack to create from the top-down, but not the bottom up. For top-down, it's essentially this:

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

自下而上，我看不出它应该如何工作.这就是我卡住的地方:

From the bottom up, I can't see how it should work. This is where I get stuck:

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])
      // ??
    }
  }
}

推荐答案

将任何递归代码机械地转换为堆栈机器并非易事.自动状态转换会产生非常复杂的代码，想想 C#-s 或 BabelJS-s 生成器.但可以肯定的是，它可以完成，但您将需要可变堆栈帧和/或寄存器.让我们看看我们面临的问题:

It's not trivial to mechanically transform any recursive code into a stack machine. Automatic stateful transformations produce very complex code, just think of C#-s or BabelJS-s generators. But sure, it can be done, but you will need mutable stackframes and/or registers. Let's see the problems we are facing:

我们必须在堆栈本身上存储一些状态变量/指令指针.这就是您使用 "open" 和 "close" 标记模拟的内容.

We have to store some state variable/instruction pointer on the stack itself. This is what you are emulating with the "open" and "close" markers.

有很多方法:

  • 将其存储在临时寄存器中
  • 向函数传递对字段的引用((对象，字段名)对)，模拟 out 参数
  • 像@CtheSky 那样使用第二个堆栈

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

Using mutable stack frames and a result register the transformed code would look something like this:

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

相关文章