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.

`I've attempted multiple times to refactor this to use iteration instead of recursion` Why? What problem are you trying to solve by doing that? Also, you question could be improved if you included a description of what your code is supposed to be doing. — Matt Burland, Apr 28 '14 at 18:48
You're trying to change a naturally recursive function into an iterative version. That's a difficult and error prone process. Are you sure you want to make that switch? It won't make the code magically faster or anything. — cassandracomar, Apr 28 '14 at 18:50
I'm trying to determine if the refactor will help with slowness in IE. I know this type of refactor is micro optimization, but in this case, every ms saved helps greatly; the recursive call stack is HUGE when I profile it in Chrome developer tools. — James Wilson, Apr 28 '14 at 18:51
Well, by refactoring to an iterative function you will need to take care of the element stack manually - not easy. To make this run slower in IE, microoptimisation (if this is one at all) will not help. Rather look in the DOM stuff like `querySelector` and try to make that faster. Try not to store the data in the DOM, so that you can iterate/recurse the tree without querying the DOM. — Bergi, Apr 28 '14 at 19:02

plalx · Answer 1 · 2014-04-28T19:28:52.663

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

Achal Dave · Accepted Answer · 2014-09-07T18:50:58.317

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

thanks, this got me close enough. This did help me identify that the recursion wasn't the problem. Now I'm thinking that the repeated use of appendChild is what's slowing me me down in IE. As each document fragment gets larger, appendChild takes longer and longer in IE. Chrome does not have this same issue. — James Wilson, Apr 28 '14 at 21:49
Perhaps something like this might help: http://stackoverflow.com/questions/9598916/speed-efficiency-of-multiple-dom-appendchild [Also, if you found a bug in the code or fixed something, please do edit the response :)] — Achal Dave, Apr 28 '14 at 22:13
You might want to look at [Document.Fragment](https://developer.mozilla.org/en-US/docs/Web/API/DocumentFragment). You can 'batch' up a bunch of things then only update the DOM once. — Jeremy J Starcher, Apr 29 '14 at 04:29

Refactoring recursive function

2 Answers2