How to convert bottom-up recursive algorithm to it

Question

Given the following 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
}

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

Answer 1

This is a solution using two stacks.

Suppose we always compute right child before left child, we need a way to store the result of right child. It's possible to store it on the original stack but it would be complicated since that stack is used to compute left child too. So I use another stack to store those results of right children.

There are three status:

• need work -> need to push child onto stack to compute
• need merge -> wait left&right child to be computed
• finish work -> all work has been done

When it sees a node with status finish work, it will check if the next node's status is need merge:

• if it's not, the current finished node is the right child, push it to the cache stack. And ready to compute left child.
• if it is, the current finished node is the left child, pop from stack and cache stack to get the root and right child, construct new node and push it back to stack with status finish work

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

function Klass(i, l, r) {
  this.i = i;
  this.l = l;
  this.r = r;
}

function create(i, growto) {
    var stack = [];
    var cache = [];

    stack.push([i, 'need work']);
    while (stack.length && stack[0][1] !== 'finish work') {
        var cur = stack.pop();
        var val = cur[0];
        var status = cur[1];

        if (status === 'need work') {
            if (val !== growto) {
                stack.push([val, 'need merge']);
                stack.push([val + 1, 'need work']);
                stack.push([val + 1, 'need work']);
            } else {
                stack.push([val, 'finish work']);
            }
        } else if (status === 'finish work') {
            if (stack[stack.length - 1][1] !== 'need merge') {
                cache.push(cur);
            } else {
                var root = stack.pop()[0];
                var left = cur[0];
                var right = cache.pop()[0];
                stack.push([new Klass(root, left, right), 'finish work']);
            }
        }
    }

    return stack.pop()[0];
}

Answer 2

What about something like this:

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

function create(depth) {
    let n = Math.pow(2, depth);
    let nodes = [];
    for (let i = 0; i < n; i++)
        nodes.push(new Klass(depth));
    for (depth--; depth >= 0; depth--) {
        let next = [];
        while (nodes.length > 0)
            next.push(new Klass(depth, nodes.pop(), nodes.pop()));
        nodes = next;
    }
    return nodes[0];
}

function Klass(i, l, r) {
  this.i = i
  this.l = l
  this.r = r
}

The call to get the same result would be create(4);. It is not exactly the same creation order, it creates the nodes from bottom to top, while recursive is like:

   7
 3   6
1 2 4 5

You can also mimick this behavior with a stack:

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

function create(depth) {
  let stack = [{depth: 0}]
  for (;;) {
    let i = stack.length - 1
    let cur = stack[i]
    if (typeof cur.left === 'undefined') {
      if (cur.depth < depth) {
        stack.push({depth: cur.depth + 1, parent: i, pos: 'right'})
        stack.push({depth: cur.depth + 1, parent: i, pos: 'left'})
      } else {
        stack[cur.parent][cur.pos] = new Klass(cur.depth)
        stack.pop()
      }
    } else {
      let node = new Klass(cur.depth, cur.left, cur.right)
      if (cur.depth == 0)
        return node
      stack[cur.parent][cur.pos] = node
      stack.pop()
    }
  }
}

function Klass(i, l, r) {
  this.i = i
  this.l = l
  this.r = r
}

The right node is pushed first on the stack and then the left node, so that the left node is higher in the stack and processed first.

Answer 3

Let's start with just the is:

function create(i) {
  console.log(i)

  if (i == 3) 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
}

console.log(JSON.stringify(create(0)))

console.log('\nStack version:')

let stack = [0];

while (stack.length){
  let i = stack.pop();

  console.log(i);

  if (i < 3)
    stack.push(i + 1, i + 1);
}

There are so many ways we could use the iteratively generated order of is; from pushing them all to an array, then following the trail of assignments backwards; to using the i to create a new Klass and passing it by reference, essentially turning the process into top-down.

Answer 4

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:

How does the machine remember where to continue the execution of a function?

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.

Where to put the result of a function?

There are many ways:

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