Refactoring recursive function

Question

I've attempted multiple times to refactor this to use iteration instead of recursion but I just can't wrap my head around it. Maybe it has something to do with the recursion happening within a loop. Assistance, even just pseudo-code, would be extremely appreciated.

var getElementAndDescendants = function (el) {
    var docFrag = document.createDocumentFragment();

    var children = el.parentElement.querySelectorAll("tr[data-parentid='" + el.getAttribute("data-myid") + "']");

    docFrag.appendChild(el);

    var len = children.length;
    for (var index = 0; index < len; index++) {
        docFrag.appendChild(getElementAndDescendants(children[index]));
    }

    return docFrag;
};

Update: This is just a small piece of a larger function that attempts to sort a pseudo-tree in the DOM made out of TR's that have children TR's in the same table. Each of those children can have their own children. The solution ends up being a recursive function within which lies the recursive function you see here. Hence why I'm after the micro optimization (if there is any to be had). I tried to keep the question simple and thus removed the outer function.

Answer 1

Something like the following should work, but treat it as pseudocode.

function getElementAndDescendants(el) {
  /* Keep a last in first out list of elements to "solve." */
  var stack = [];
  /* Store solutions here. */
  solutions = {};

  stack.push(el);

  while (stack.length != 0) {
    var el = stack.pop();

    var docFrag = document.createDocumentFragment();
    var children = el.parentElement.querySelectorAll("tr[data-parentid='" + el.getAttribute("data-myid") + "']");
    var children_len = children.length;

    if (!el in solutions && children_len != 0) {
      stack.push(el);

      /* This way, next time we get to me, we know my children were queued
       * up earlier and must have been solved. */
      solutions[el] = null;

      /* My children are not solved; queue them and solve them first. */
      for (var i = 0; i < children_len; ++i) {
        stack.push(children[i]);
      }
    } else {
      /* Me and my children are solved! Pull me off the stack and solve. */
      stack.pop();

      docFrag.appendChild(el);

      /* The children must have been solved, if there are any. */
      for (var i = 0; i < children_len; ++i) {
        docFrag.appendChild(solutions[el]);
      }

      solutions[el] = docFrag;
    }
  }
}

Answer 2

Like @Bergi stated already, going from recursive to iterative might not increase performance significantly (or will perhaps be slower... gotta jsperf!). The main reason to ditch recursion is when you encouter some stack overflow issues when processing large trees.

You should definitely avoid storing your data in the DOM instead.

However, here's a depth-first tree iteration example that I created for you:

var tree = {
    title: 'root',
    children: [
        { title: 'node 1' },
        { 
                    title: 'node 2',
                    children: [
                        { title: 'node 5' },
                        { title: 'node 6' }
                    ] 
                },
        { title: 'node 3' },
        { 
            title: 'node 4',
            children: [
                { title: 'node 7' }
            ]
        }
    ]
};

function dfsIterativePrintTree(node) {
    var queue = [node], i, children;

    while (node = queue.pop()) {        
        children = node.children || [];         
        //loop backward, otherwise the nodes will be traversed backward because
        //we pop the nodes.
        for (i = children.length; i--;) queue.push(children[i]);

        console.log(node.title);
    }
}

dfsIterativePrintTree(tree);