CODEWITHSUNDEEP
javascriptc#recursion
Oleksandr Hrebeniuk
Oleksandr Hrebeniuk

Reputation: 165

How to avoid "maximum call stack size exceeded" exception?

I have the next code for generating sitemap tree by urls list. C# model:

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# method that generates list of nodes.

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 code. Next function takes list of nodes:

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

And next one called recursively:

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

This code works good for a small set of data. But when I try to pass list of 500 nodes I get next error:

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

So, the question is how I can optimize code to avoid this error?

Upvotes: 1

Views: 6462

Answers (1)

Bryan Euton
Bryan Euton

Reputation: 929

There are two ways that you can fix this issue. You always have to worry about the call stack size when you use recursive functions. If you believe it is an issue, then you need to go asynchronous or refactor to not be recursive. These aren't necessarily the most optimized answers but hopefully they'll get you started.

Non-Recursive function

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

Asynchronous Recursive function

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

I used the following to create trees for testing the code:

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

Use the following snippet to call the two functions with the test nodes: Note: the following uses jquery to get the body node. I called the following snippet when the page was ready.

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

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

Upvotes: 4

Related Questions