Why is this recursive algorithm in JS not working?

Question

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?

What do you want to end up with? You're overwriting the elements of rs each time. — pimvdb
– pimvdb, Commented Dec 26, 2011 at 22:58
possible duplicate of JavaScript recursive Element creation fails — outis
– outis, Commented Dec 26, 2011 at 23:42
This seems a really odd way to cycle through the possibly combinations: wouldn't a nested for loop do the trick in a much more readable way? Even the desired output in the comment at the end of your code seems a bit strange because you've got lots of repeated values. Why does your function return 0 when you don't use the return at all? — nnnnnn
– nnnnnn, Commented Dec 27, 2011 at 2:38
Well, this is a simplified version... In the real one, it's not just 0's and 1's but other numbers too, and the there are 15 elements of rs, not just three... This is the first thing I came up with, do you have a better solution? This is very slow, and yes, repeats things (although functions correctly). — corazza
– corazza, Commented Dec 27, 2011 at 8:16

Pointy · Accepted Answer · 2011-12-26 22:52:04Z

6

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].

answered Dec 26, 2011 at 22:52

Pointy

415k62 gold badges600 silver badges631 bronze badges

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

6 Comments

corazza Over a year ago

Thanks for the answer! I had previous difficulties with the global scope and not declaring variables with the var keyword... Should I do function(var cS) as well? Kinda like in C++, where you have to initialize the funtion's argumenta. Oh yeah, and this is just the simplified version, in the actual one I do do stuff with these permutations, and it's not just 0's and 1's but other numbers as well.

juandopazo Over a year ago

No, JavaScript doesn't require keywords for parameters. If you're just starting with JS, a good introduction is the free book Eloquent JavaScript: eloquentjavascript.net

Pointy Over a year ago

@bane parameters are always like local variables (though in some arcane ways they're not exactly like local variables).

corazza Over a year ago

That's good! I'm gonna test it now and tell you if it works, it probably will. Can you tell me of these strange arcane ways? I'm very interested in the very nature and behaviour of programming languages and I like learning about new concepts :)

Pointy Over a year ago

@bane well I'm not as expert as some; it very rarely matters. What I do know is that in some weird way, parameters and the (also somewhat weird) arguments pseudo-variable are references to the same memory. Thus if you've got a parameter "a" as the first parameter, changes to "a" are reflected in arguments[0] and vice-versa. Like I said, it's really rare that you have to worry about that.

|

Collectives™ on Stack Overflow

Why is this recursive algorithm in JS not working?

1 Answer 1

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related