Strange behaviour of for loop in Heap's algorithm in JavaScript

Question

I'm trying to implement Heap's algorithm to find different permutations of a string and found a strange behaviour with a for loop, here's the code

function permAlone(str) {

  var strArr = str.split(''),
  permutations = [];

  function swap(strArr, x, y) {
    var tmp = strArr[x];
    strArr[x] = strArr[y];
    strArr[y] = tmp;
  }

  function generate(n) {
    if (n === 1) {
        permutations.push(strArr.join());
    } else {
        for (var i = 0; i != n; i++) {
        generate(n - 1);
        swap(n % 2 ? 0 : i, n - 1);        
      }
    }
  }

  generate(strArr.length);

  return permutations;
}

console.log(permAlone('aab'));

In the for loop within the generate function, if I put i = 0 the output of the script is ['a,a,b', 'a,a,b'] but if I put var i = 0 the output is ['a,a,b', 'a,a,b', 'a,a,b', 'a,a,b', 'a,a,b', 'a,a,b'].

I understand that var i would create a local variable for the loop, but don't understand in this case why it would change how the loop functions as there is no i variable declared anywhere else in the script.

Thanks any help appreciated.

With variable i local to the function generate there will be one i each for each function call for generate which correspond to separate memory locations. With variable i being global all function calls are using the same i in memory and each call doesn't create its own i. (Just my version of the above explanation) — sabithpocker
– sabithpocker, Commented Apr 30, 2016 at 8:34

nnnnnn · Accepted Answer · 2016-04-30 08:33:59Z

2

The reason the behaviour changes if you have a global i variable is that you have multiple recursive calls to generate() all trying to control their own partially complete for loops with the same variable, and all setting i back to 0 when they start.

Picture what happens on the second iteration of the for loop: i is 1 because it has just been incremented, but then immediately a recursive call to generate() starts its own loop and sets i back to 0 again.

If you create a local variable with var then each for loop in each recursive call is independent of all the others.

Try stepping through the code with the debugger, or try adding the following as the first line inside the for loop and watch what happens to the variables when the code runs:

 console.log('n:' + n + '; i: '+i);

answered Apr 30, 2016 at 8:33

nnnnnn

150k30 gold badges210 silver badges247 bronze badges

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

Collectives™ on Stack Overflow

Strange behaviour of for loop in Heap's algorithm in JavaScript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related