turning recursion into iteration in JS

1-recursive.js

// Version 1. Simple recursive function. Blows the stack for large nodes.
function replace(node, from, to) {
    switch (node.type) {
      case IF:
        return {
            type: IF,
            test: replace(node.test, from, to),
            then: replace(node.then, from, to),
            else: replace(node.else, from, to)
        };

      case ID:
        return {
            type: ID,
            name: node.name.replace(from, to)
        };

      case SEQ:
        return {
            type: SEQ,
            nodes: node.nodes.map(function(node) {
                return replace(node, from, to);
            });
        };

      // etc.
    }
}

2-cps.js

// Version 2. CPS. Still blows the stack because of lack of proper tail calls.
function replace(node, from, to, k) {
    switch (node.type) {
      case IF:
        return replace(node.test, from, to, function(testNode) {
            return replace(node.then, from, to, function(thenNode) {
                return replace(node.else, from, to, function(elseNode) {
                    return k({
                        type: IF,
                        test: testNode,
                        then: thenNode,
                        else: elseNode
                    });
                });
            });
        });

      case ID:
        return k({
            type: ID,
            name: node.name.replace(from, to)
        });

      case SEQ:
        return mapCPS(node.nodes, function(node, k) {
            return replace(node, from, to, k);
        }, k);

      // etc.
    }
}

function mapCPS(a, f, k) {
    var i = 0, n = a.length;
    var result = [];
    return (function loop() {
        if (i > n)
            return k(result);
        return f(a[i], function(x) {
            result[i] = x;
            i++;
            return loop();
        });
    })();
}

3-loops.js

// Version 3. Iterative. No more modularization; one monolithic loop.
const TOP = 0,
      IF_TEST = 1,
      IF_THEN = 2,
      IF_ELSE = 3,
      SEQ_ENTRY = 4;

function replace(node, from, to) {
    var stack = [{ type: TOP }];
    var result;

  recursion:
    while (stack.length) {

      pushing:
        while (true) {
            switch (node.type) {
              case IF:
                stack.push({
                    type: IF_TEST,
                    then: node.then,
                    else: node.else
                });
                node = node.test;
                continue pushing;

              case ID:
                result = {
                    type: ID,
                    name: node.replace(from, to);
                };
                break pushing;

              case SEQ:
                if (!node.nodes.length) {
                    result = node;
                    break pushing;
                }
                stack.push({
                    type: SEQ_ENTRY,
                    length: node.nodes.length,
                    nodes: node.nodes,
                    index: 0,
                    results: []
                });
                node = node.nodes[0];
                continue pushing;

              // etc.
            }
        }

      popping:
        while (true) {
            var top = stack.pop();
            switch (top.type) {
              case TOP:
                return result;

              case IF_TEST:
                node = top.then;
                stack.push({
                    type: IF_THEN,
                    test: result,
                    else: top.else 
                });
                continue recursion;

              case IF_THEN:
                node = top.else;
                stack.push({
                    type: IF_ELSE,
                    test: top.test,
                    then: result
                });
                continue recursion;

              case IF_ELSE:
                result = {
                    type: IF,
                    test: top.test,
                    then: top.then,
                    else: result
                };
                continue popping;

              case SEQ_ENTRY:
                if (top.index >= top.length) {
                    result = top.entries;
                    continue popping;
                }
                top.results[top.index] = result;
                stack.push({
                    type: SEQ_ENTRY,
                    length: top.length,
                    nodes: top.nodes,
                    index: top.index + 1,
                    results: top.results
                });
                node = top.results[top.index + 1];
                continue recursion;
            }
        }
    }
}

4-trampoline.js

// Version 4. CPS with a trampoline to prevent stack growth. Modular and iterative
// (but more expensive than loops).

// a trampoline computation is either done with a result or a thunk with more work to do:
// 
// comp<a> = Done(a)
//         | function() -> comp<a>

function Done(x) {
    this.value = x;
}

// trampoline :: function(function(a ...) -> comp<b>) -> function(a ...) -> b
function trampoline(f) {
    return function() {
        for (var next = f.apply(this, arguments); typeof next === "function"; next = next())
            ;
        return next.value;
    };
}

// replace :: function(node, string, string) -> node
function replace(node, from, to) {
    return (trampoline(replaceCPS))(node, from, to, function(x) {
        return new Done(x)
    });
}

// replaceCPS :: function(node, string, string, function(node) -> comp<node>) -> comp<node>
function replaceCPS(node, from, to, k) {
    switch (node.type) {
      case IF:
        return function() {
            return replaceCPS(node.test, from, to, function(testNode) {
                return function() {
                    return replaceCPS(node.then, from, to, function(thenNode) {
                        return function() {
                            return replaceCPS(node.else, from, to, function(elseNode) {
                                return k({
                                    type: IF,
                                    test: testNode,
                                    then: thenNode,
                                    else: elseNode
                                });
                            });
                        };
                    });
                };
            });
        };

      case ID:
        return k({
            type: ID,
            name: node.name.replace(from, to)
        });

      case SEQ:
        return mapCPS(node.nodes, function(node, k) {
            return replaceCPS(node, from, to, k);
        }, k);

      // etc.
    }
}

// mapCPS :: function([a],
//                    function(a, function(b) -> comp<c>) -> comp<c>,
//                    function([b]) -> comp<c>)
//        -> comp<c>
function mapCPS(a, f, k) {
    var i = 0, n = a.length, result = [];
    return (function loop() {
        if (i >= n)
            return k(result);
        return f(a[i], function(x) {
            result[i] = x;
            i++;
            return loop;
        });
    })();
}