javascript - 重构递归函数

Question

我曾多次尝试重构它以使用迭代而不是递归，但我就是无法理解它。也许它与循环内发生的递归有关。非常感谢您提供帮助，即使只是伪代码。

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

更新:这只是一个较大函数的一小部分，它试图对 DOM 中的伪树进行排序，该伪树由同一个表中具有子 TR 的 TR 构成。这些 child 中的每一个都可以有自己的 child 。该解决方案最终成为一个递归函数，其中包含您在此处看到的递归函数。因此，为什么我要进行微优化(如果有的话)。我试图使问题简单化，因此删除了外部函数。

Answer 1

就像@Bergi 已经说过的那样，从递归到迭代可能不会显着提高性能(或者可能会更慢......必须使用 jsperf!)。放弃递归的主要原因是当您在处理大型树时遇到一些堆栈溢出问题。

您绝对应该避免将数据存储在 DOM 中。

但是，这是我为您创建的深度优先树迭代示例:

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