如何在JavaScript中将自下而上的递归算法转换为迭代堆栈 [英] How to convert bottom-up recursive algorithm to iterative stack in 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 em>，在创建所有子项之后，递归地。因此它首先创建叶节点，然后将其传递给父节点等。

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这样的第二个堆栈

• storing it in a temporary register
• passing the function a reference to a field (an (object, fieldname) pair), emulating out parameters
• using a second stack like @CtheSky did

使用可变堆栈帧和结果寄存器，转换后的代码看起来像这样：

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

这篇关于如何在JavaScript中将自下而上的递归算法转换为迭代堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！