CODEWITHSUNDEEP
javascriptrecursion
paddle42380
paddle42380

Reputation: 7081

Problem with simple Recursion in Javascript

Here is the code snippet, this goes into an infinite loop - with the "too much recursion error".

SW = {
    WData : {
        wf : {

            roots : [852,1517,1523,1540],
            leaves : [],
            features : {
                852:  { "cf":"855,1848"},
                1517: { "cf":"1929,1930"},
                1523: { "cf":""},
                1540: { "cf":"1546,1549"},
                855:  { "cf":"" },
                1848: { "cf":""},
                1929: { "cf":""},
                1930: { "cf":""},
                1546: { "cf":"1600"},
                1549: { "cf":""},
                1600: { "cf":""}                
            }
        }
    },

    init: function init(){                
        this.buildTree();
        //console.log(this.WData.wf.leaves);
    },

    buildTree : function(){
        this.getLeaves(this.WData.wf.roots);
    },

    getLeaves: function(roots){
        for(var i in roots){
            var root = this.WData.wf.roots[i];

            if( this.WData.wf.features[ root ].cf === ""){

                this.WData.wf.leaves.push( root );
                return false;
            }
            else{
                this.getLeaves( this.WData.wf.features[root].cf.split(',').map(Number) );
            }
        }
        return false;
    }
}


SW.init();

Not able to understand what is the problem here. I have a feeling i am making quite a simple mistake.

http://jsfiddle.net/eWGG8/4/

Upvotes: 1

Views: 1034

Answers (4)

FK82
FK82

Reputation: 5075

From what I can tell, you need to change the values of the cf properties in the features entries to reflect that you already parsed them. If you don't, this branch of your code

else{
    this.getLeaves( this.WData.wf.features[root].cf.split(',').map(Number) );
}

will infinitely add values to the leaves Array, if I'm correct.

So, try adding something like:

 else {

    var cf = this.WData.wf.features[root].cf ; // save the current cf value

    //... change this.WData.wf.features[root].cf to the desired value

        this.getLeaves( cf.split(',').map(Number) ) ;


 }

By the way, Array.map is a browser implementation specific function (for Gecko browsers, e.g. Firefox). In other words your code won't work where that is not implemented.

Also, in my opinion, you would do good to add comments and fold out your code to make it more readily understandable. The way it is written now it is terse but hard to grasp its essential purpose.

Upvotes: 0

a'r
a'r

Reputation: 37029

You have a couple of problems:

  1. At the start of your loop, you should be using roots rather than this.WData.wf.roots, eg. like this:

    var root = roots[i];

  2. You are trying to push new items onto a string rather than an array, so in your structure, change leaves to the following:

    leaves : ["asdf"],

  3. This then results in an error when you try to assign it to your results div (in the jsFiddle), so use join to create a string

    $('#result').append( SW.WData.wf.leaves.join(",") );

Upvotes: 1

selbie
selbie

Reputation: 104599

You keep referencing the original tree in your recursion - you likely want to split on the node that you passed in recursively:

getLeaves: function(roots){
for(var i in roots){
    var root = roots[i];

    if( !(root.cf)){

        this.WData.wf.leaves.push( root );
        return false;
    }
    else{
        this.getLeaves( root.cf.split(',').map(Number) );
    }
}
return false;

Upvotes: 0

Michael Dillon
Michael Dillon

Reputation: 32392

Your termination condition is in this line:

for(var i in roots){

so why not follow it up with something like this console.log(i) to see if it is doing what you think. This type of technique is often faster than a debugger.

Upvotes: 0

Related Questions