How to convert bottom-up recursive algorithm to iterative stack in JavaScript

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

Just a pointer, looping and pushing to same array can be injurious to health! If you reverse the initial insertions, it might become a never ending loop. — Rajesh Dixit
– Rajesh Dixit, Commented Jan 18, 2018 at 5:14

Tamas Hegedus · Accepted Answer · 2018-01-18 16:20:17Z

3

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

answered Jan 18, 2018 at 16:20

Tamas Hegedus

30.1k12 gold badges67 silver badges102 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Lance Pollard Over a year ago

This is more along the lines of what I was looking for. Thank you.

גלעד ברקן Over a year ago

Great implementation.

גלעד ברקן · Accepted Answer · 2018-01-18 15:25:32Z

2

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

edited Jan 18, 2018 at 15:25

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

answered Jan 18, 2018 at 10:46

CtheSky

2,63416 silver badges16 bronze badges

2 Comments

CtheSky Over a year ago

please leave a comment if downvoted, I want to know why

גלעד ברקן Over a year ago

(If you click on the vote count of your answer, it will show you the vote breakdown. There are currently no downvotes. My vote was the first +1, then I removed it, and now voted it up again :)

maraca · Accepted Answer · 2018-01-18 11:56:06Z

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.

גלעד ברקן · Accepted Answer · 2018-01-18 16:12:12Z

0

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.

edited Jan 18, 2018 at 16:12

answered Jan 18, 2018 at 14:29

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

Collectives™ on Stack Overflow

How to convert bottom-up recursive algorithm to iterative stack in JavaScript

4 Answers 4

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

Where to put the result of a function?

2 Comments

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

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

Where to put the result of a function?

2 Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related