如何避免「超出最大調用堆棧大小」異常？

Question

我有通過網址列表生成網站地圖樹的下一個代碼。 C＃模型：

，其生成節點列表

public class Node 
{ 
    public Node(string child, string parent) 
    { 
     Child = child; 
     Parent = parent; 
    } 
    public string Parent { get; set; } 
    public string Child { get; set; } 
    public bool IsRoot { get; set; } 
} 

C＃方法。

private static List<Node> ExtractNode(List<string> Urls) 
    { 
     List<Node> nodeList = new List<Node>(); 

     foreach (string itm in Urls) 
     { 
      string[] arr = itm.Split('/'); 
      int index = -1; 

      foreach (string node in arr) 
      { 
       index += 1; 
       if (index == 0) 
       { 
        Node rootNode = new Node(node, ""); 
        if (!nodeList.Exists(x => x.Child == rootNode.Child & x.Parent == rootNode.Parent)) 
        { 
         rootNode.IsRoot = true; 
         nodeList.Add(rootNode); 
        } 
       } 
       else 
       { 
        Node childNode = new Node(node, arr[index - 1].ToString()); 
        { 
         if (!nodeList.Exists(x => x.Child == childNode.Child & x.Parent == childNode.Parent)) 
         { 
          nodeList.Add(childNode); 
         } 
        } 
       } 
      } 
     } 
     return nodeList; 
    } 

Javascript代碼。接下來函數採用節點列表：

function makeTree(nodes) { 
var roots = []; 
for (var i = 0; i < nodes.length; i++) { 
    if (nodes[i].IsRoot) { 
     roots.push(nodes[i].Child); 
    } 
} 
var trees = ""; 
for (var j = 0; j < roots.length; j++) { 
    trees += "<div class='sitemapRoot'><ul><li>" + getChildren(roots[j], nodes) + "</li></ul></div>"; 
} 
return trees; 
} 

而下一個遞歸調用：

function getChildren(root, nodes) { 
var result = ""; 
var index = 0; 
for (var i = 0; i < nodes.length; i++) { 
    if (nodes[i].Parent == root) { 
     index += 1; 
    } 
} 

if (index > 0) { 
    var RootHeader = ""; 
    for (var j = 0; j < nodes.length; j++) { 
     if (nodes[j].IsRoot & root == nodes[j].Child) { 
      RootHeader = nodes[j].Child; 
     } 
    } 
    result += RootHeader + "<ul>\n"; 
    for (var k = 0; k < nodes.length; k++) { 
     if (nodes[k].IsRoot & root == nodes[k].Child) { 
      RootHeader = nodes[k].Child; 
     } 
     if (nodes[k].Parent == root) { 
      result += "<ul><li>" + nodes[k].Child + getChildren(nodes[k].Child, nodes) + "</li></ul>\n"; 
     } 
    } 
    result += "</ul>\n"; 
    return result; 
} 
return ""; 
} 

此代碼很好的一個小的數據集。但是，當我試圖通過500個節點的名單，我得到一個錯誤：

Uncaught RangeError: Maximum call stack size exceeded at getChildren (treeGenerator.js:371)

所以，問題是我怎麼可以優化代碼來避免這個錯誤？

Answer 1

有兩種方法可以解決此問題。當你使用遞歸函數時，你總是不得不擔心調用堆棧的大小。如果你認爲這是一個問題，那麼你需要去異步或重構不能遞歸。這些不一定是最優化的答案，但希望他們能讓你開始。

非遞歸函數

function makeTree(nodes) { 
    var roots = [], 
     limbs = [], 
     i, j; 

    //go through all of the nodes and link the parent/children. 
    for (i = 0; i < nodes.length; i++) { 
     for (j = i + 1; j < nodes.length; j++) {//only look at the rest of the elements to increase performance 
      if (nodes[i].Child == nodes[j].Parent) { 
       nodes[i].children = (nodes[i].children || []); 
       nodes[i].children.push(nodes[j]); 
       nodes[j].parentNode = nodes[i]; 
      } 
     } 
     for (j = 0; j < limbs.length; j++) {//look through the limbs to see if one of them is my child. 
      if (nodes[i].Child == limbs[j].Parent) { 
       nodes[i].children = (nodes[i].children || []); 
       nodes[i].children.push(limbs[j]); 
       limbs[j].parentNode = nodes[i]; 
       limbs.splice(j--, 1);//remove from the list since I can only have 1 parent. 
      } 
     } 
     //I have all of my children. 
     if (nodes[i].IsRoot) { 
      roots.push(nodes[i]); 
     }else if(!nodes[i].parentNode){ 
      //I don't know my parent so I'm a limb. 
      limbs.push(node); 
     } 

    } 
    //now that everyone knows their parent and their children, we'll assemble the html by looking at all of the leafs first and working way up the tree. 
    i = 0; 
    while(nodes.length > 0){ 
     if(!nodes[i].children || nodes[i].childHtml){ 
      //I'm either a leaf or I have my child's html. 
      var node = nodes[i]; 
      node.html = node.Child + (node.childHtml? "<ul>" + node.childHtml + "</ul>" : ""); 
      node.childHtml = null;//don't need this anymore. 
      if(node.parentNode){ 
       //let's check to see if my siblings are complete 
       var ready = true, 
        childHtml = ""; 
       for(var j = 0; j < node.parentNode.children.length; j++){ 
        if(node.parentNode.children[j].html == null){ 
         ready = false;//I don't know this html yet so skip it for now. 
         break; 
        }else{ 
         childHtml += "<li>" + node.parentNode.children[j].html + "</li>";//go ahead and try to create the list of children. 
        } 
       } 
       if(ready){ 
        //all of siblings are complete, so update parent. 
        node.parentNode.childHtml = childHtml; 
        node.parentNode.children = null;//remove reference for cleanup. 
       } 
      } 
      nodes.splice(i, 1);//remove from the list since I have my html. 
     }else{ 
      i++;//look at the next node in the list. 
     } 
     if(i >= nodes.length){ 
      i = 0;//since we are splicing and going through the list multiple times (possibly), we'll set the index back to 0. 
     } 
    } 

    //every node knows it's html, so build the full tree. 
    var trees = ""; 
    for (var j = 0; j < roots.length; j++) { 
     trees += "<div class='sitemapRoot'><ul><li>" + roots[j].html + "</li></ul></div>"; 
    } 
    return trees; 
} 

異步遞歸函數

function makeTreeAsync(nodes, callback) { 
    var roots = [], 
     numRoots = 0; 
    for (var i = 0; i < nodes.length; i++) { 
     if (nodes[i].IsRoot) { 
      numRoots++; 
      getChildrenAsync(nodes[i], nodes, create); 
     } 
    } 
    function create(child){ 
     roots.push(child); 
     if(roots.length === numRoots){ 
      var trees = ""; 
      for (var j = 0; j < roots.length; j++) { 
       trees += "<div class='sitemapRoot'><ul><li>" + roots[j].html + "</li></ul></div>"; 
      } 
      callback(trees); 
     } 
    } 
} 
function getChildrenAsync(root, nodes, callback) { 
    var result = ""; 
    var index = 0; 
    var children = []; 
    for (var i = 0; i < nodes.length; i++) { 
     if (nodes[i].Parent == root.Child) { 
      index += 1; 
      getChild(i); 
     } 
    } 

    if (index == 0) { 
     root.html = root.Child; 
     callback(root); 
    } 
    function getChild(x){ 
     setTimeout(function(){ 
      getChildrenAsync(nodes[x], nodes, createHtml); 
     }); 
    } 
    function createHtml(node){ 
     children.push(node); 
     if(children.length === index){  
      var result = root.Child; 
      if(children.length){ 
       result += "<ul>" 
       for (var j = 0; j < children.length; j++) { 
        result += "<li>" + children[j].html + "</li>"; 
       } 
       result += "</ul>"; 
      } 
      root.html = result; 
      callback(root); 
     } 
    } 
} 

我用下面爲測試代碼創建樹：

function makeTestNodes(numRoots, numChildrenPerRoot){ 
    var nodes= []; 
    for(var i = 0;i < numRoots;i++){ 
     nodes.push({ 
      Parent: "", 
      Child: i.toString(), 
      IsRoot: 1 
     }); 
     var parent = i.toString(); 
     for(var j = 0;j < numChildrenPerRoot;j++){ 
      var child = parent + "." + j.toString(); 
      nodes.push({ 
       Parent: parent, 
       Child: child, 
       IsRoot: 0 
      }); 
      nodes.push({ 
       Parent: parent, 
       Child: parent + "." + j.toString() + "a", 
       IsRoot: 0 
      }); 
      parent = child; 
     } 
    } 
    return nodes; 
} 

使用下面的代碼片段調用具有測試節點的兩個功能： 注意：下面使用jquery獲取body節點。當頁面準備就緒時，我會調用以下代碼片段。

var body = $("body"); 
body.append(makeTree(makeTestNodes(20, 50))); 

makeTreeAsync(makeTestNodes(20, 50), function(html){ 
    body.append(html); 
});