CODEWITHSUNDEEP
javascriptrecursiontreedepth-first-search
Ernestas Romeika
Ernestas Romeika

Reputation: 171

Javascript, strange recursion behavior, DFS

So I had a simple task to implement DFS in Javascript. What seemed like it will be a quick work turned into never-ending witch hunt. The idea of assignment was to imitate multiple-parent behavior, by finding the first "inherited" function in dfs manner. The first implementation was working well, but after a lot of testing I found out that it doesn't visit some of the branches, sometimes. After 2 days, I boiled it down to this simplest case, deleted most of the code to make it as straight-forward as possible. So here's the function that creates a tree node:

function myObject(parentArgs){
    var node = {};
    node.parents = [];
    node.hasParents = function(){return this.parents.length>0};
    for(i = 0; i<parentArgs.length; i++){
        node.parents.push(parentArgs[i]);
    }

    node.call = function(fun,args){
        if(this[fun] != null)
            return this[fun].apply(this,args);
        var res = null;
        for(i=0;i<this.parents.length; i++){
            res = this.parents[i].call(fun,args);
            if(res!=null)
                break;
        }
        return res;
    }    
    return node;
}
myObject.create = function(args){
    return myObject(args);
}

And here are the tests:

1 (works):

var c1 = myObject.create([]);
var c2 = myObject.create([]);
c2.func = function(args){return "func2: " + args;};
var c3 = myObject.create([c1,c2]);
var c4 = myObject.create([]);
var c5 = myObject.create([c3]);
var c6 = myObject.create([c4,c5]);
alert(c6.call("func",["hello"]));

2 (doesn't work):

var c0 = myObject.create([]);  //this line was added
var c1 = myObject.create([c0]); //c0 assigned as parent
var c2 = myObject.create([]);
c2.func = function(args){return "func2: " + args;};
var c3 = myObject.create([c1,c2]);
var c4 = myObject.create([]);
var c5 = myObject.create([c3]);
var c6 = myObject.create([c4,c5]);
alert(c6.call("func",["hello"]));

And even simpler case:

3 (works):

var c1 = myObject.create([]);
var c2 = myObject.create([]);
c2.func = function(args){return "func2: " + args;};
var c3 = myObject.create([c1,c2]);
alert(c3.call("func",["hello"]));

4 (doesn't work):

var c0 = myObject.create([]);  //this line was added
var c1 = myObject.create([c0]); //c0 assigned as parent
var c2 = myObject.create([]);
c2.func = function(args){return "func2: " + args;};
var c3 = myObject.create([c1,c2]);
alert(c3.call("func",["hello"]));

What's stranger, is that c0 is in a different branch from c2, so it shouldn't be affected at all. I'm not sure where the bug is coming from. Please note that I deleted all input checking and circular-reference checking for the sake of simplicity of this code.

Upvotes: 0

Views: 345

Answers (1)

DoctorMick
DoctorMick

Reputation: 6793

You've defined i with global scope so each time you hit a recursive call to the parent it gets incremented and you jump out of the loop in the caller. In both of your for loops change:

for(i=0...

to

for(var i=0...

That way each loop has its own instance of i and there will be no confusion. With that change both of your examples work.

Upvotes: 1

Related Questions