CODEWITHSUNDEEP
javascriptrecursion
corazza
corazza

Reputation: 32384

Why is this recursive algorithm in JS not working?

I made this simple algorithm, but Chrome is acting weird, almost like functions called recursively don't return... Algorithm's task is to cycle trough all the possibilities of the rs array, which has three elements which can be either 0 or 1.

//rs is the list of all variables that can be 0 or 1
//cS, or currentStack is the variable that s

rs = [0, 0, 0];

circ = function(cS)
{
     for (pos = 0; pos <= 1; pos ++)
     {
          rs[cS] = pos;
          if (cS + 1 < rs.length)
               circ(cS + 1);
     }
     return 0;                    
}

circ(0); //this should cycle trough all the possibilities of the rs array, it should look like this:
/*
000 - first element of rs, not last, so continue to the next
000 - second element of rs, not last, so continue to the next
000 - third element of rs, last, so continue with the for loop
001 - the for loop ends, return to the second element
011 - second element of rs, not last, so continue to the next
010 - third element of rs, last, so continue with the for loop
011 - the for loop ends, return to the first element
111 - first element of rs, not last, so continue to the next
101 - second element of rs, not last, so continue to the next
100 - third element of rs, last, so continue with the for loop
101 - the for loop ends, return to the second element
111 - second element of rs, not last, so continue to the next
110 - third element of rs, last, so continue with the for loop
111 - the for loop ends, return to the second element
111 - the for loop ends, return to the first element
111 - return
*/

However, it simply goes like this:

000
000
000
001
return

Can anyone tell me why is this happening? What did I do wrong?

Upvotes: 1

Views: 198

Answers (1)

Pointy
Pointy

Reputation: 414086

You forgot to declare "pos" with var.

var circ = function(cS)
{
     for (var pos = 0; pos <= 1; pos ++)
     {
          rs[cS] = pos;
          if (cS + 1 < rs.length)
               circ(cS + 1);
     }
     return 0;                    
}

Because you forgot var, "pos" was global, so the recusive calls would mess up the parent environment.

I can't guarantee that's the only problem here. For example in the function as written it may iterate through all the permutations, but it doesn't show them or copy them anywhere, so the end result will just be [1, 1, 1].

Upvotes: 6

Related Questions