重构递归函数

我已经多次尝试重构这个使用迭代而不是递归，但我不能换我的头周围。也许它与循环内发生的递归有关。援助，即使只是伪代码，将不胜感激。重构递归函数

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

更新：这只是一小部分，试图以按做出来TR的有孩子TR的在同一个表的DOM伪树更大的功能。每个孩子都可以有自己的孩子。该解决方案最终成为递归函数，其中包含您在此处看到的递归函数。因此，为什么我在微观优化之后（如果有的话）。我试图保持简单的问题，从而消除了外部功能。

来源

2014-04-28 James Wilson

你为什么要重构这段代码？ – zzzzBov

'我试过多次重构这个来使用迭代而不是递归'为什么？你想通过这样做解决什么问题？此外，如果您包含了代码应该执行的操作的描述，则可以改进您的问题。 –

您正在尝试将自然递归函数更改为迭代版本。这是一个困难且容易出错的过程。你确定要做这个转换吗？它不会让代码变得更快或者更快。 – acomar

类似下面应该工作，但是把它当作伪代码。

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

来源

2014-04-28 19:22:54

谢谢，这让我足够接近。这确实帮助我确定递归不是问题。现在我在想，重复使用appendChild会让我在IE中变慢。随着每个文档片段变大，appendChild在IE中占用的时间越来越长。 Chrome没有这个问题。 –

也许这样的事情可能会有所帮助：http://stackoverflow.com/questions/9598916/speed-efficiency-of-multiple-dom-appendchild [此外，如果你发现代码错误，还是一个固定的东西，请不要编辑响应:)] –

你可能想看看[Document.Fragment（https://developer.mozilla.org/en-US/docs/Web/API/DocumentFragment）。你可以'批量'一堆东西，然后只更新一次DOM。 –

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

来源

2014-04-28 19:18:06 plalx

重构递归函数

回答

相关问题