Problem with simple Recursion in Javascript

Question

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/

a'r · Accepted Answer · 2011-03-05 08:56:58Z

1

You have a couple of problems:

At the start of your loop, you should be using roots rather than this.WData.wf.roots, eg. like this:
```
var root = roots[i];
```
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"],
```
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(",") );
```

answered Mar 5, 2011 at 8:56

a'r

37.2k7 gold badges68 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Michael Dillon · Accepted Answer · 2011-03-05 08:50:02Z

0

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.

answered Mar 5, 2011 at 8:50

Michael Dillon

32.5k7 gold badges76 silver badges107 bronze badges

Comments

selbie · Accepted Answer · 2011-03-05 08:50:30Z

0

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;

answered Mar 5, 2011 at 8:50

selbie

105k15 gold badges109 silver badges187 bronze badges

Comments

FK82 · Accepted Answer · 2011-03-05 09:31:26Z

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.

Collectives™ on Stack Overflow

Problem with simple Recursion in Javascript

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related