Trying to understand recursion within for loops in javascript

Question

I've been staring at the answer to this question forever even writing down variables and whatnot through each iteration. I simply just don't get the process here. When I throw in console logs I see that permute is called input.length - 1 times before it ever gets to this line input.splice(i, 0, ch); It's hard to phrase the question when I am lost completely, but I guess some curiosities are: each time permute is called, it is a new instance of that function with it's own closure right? therefore variables changes that are within the function won't affect variables in other calls? does the function return permArr for each time it's called? and I suppose that doesn't necessarily affect the return of the first call? (my instinct tells me that the first time return happens, the function stops running).

Thanks for the insight.

Permutations in JavaScript?

var permArr = [],
usedChars = [];

function permute(input) {
  var i, ch;
  for (i = 0; i < input.length; i++) {
    ch = input.splice(i, 1)[0];
    usedChars.push(ch);
    if (input.length == 0) {
        permArr.push(usedChars.slice());
    }
    permute(input);
    input.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};

Answer 1

I'll give this a shot.

Overview

You start with two arrays that will have global scope: permArray will eventually hold all of the permutation arrays, and usedChars is a worker array used build each individual permutation array through all of the recursive calls. It's important to note that these are the only two variables that are accessible in the scope of every function created. All other variables have local scope to their own function call.

Then there is the recursive function which accepts an array as input and returns an array of array with all possible permutations of the input array. Now, in this particular function the recursive call is inside a loop. This is interesting because the terminating condition is actually more complicated than your basic recursive function--the recursive calls terminate when you pass in an empty input array and the for loop skips over the next recursive call.

Summary

Consider a four element array input. At a high level, the function is going to loop over the four elements of this array, pull out each element, and compute the permutation of that smaller array of three elements. With all of those three element permutations, it will append the original element pulled out to the beginning and add each of those four element arrays to permArray.

But, in order to find the permutation of the smaller three element arrays, we pull out each element, compute the permutation of that smaller array of two elements, add the element pulled out to the beginning of each of those permutations, and return each of those three element arrays up the recursion call stack so the original fourth element can be added to the beginning and counted as a permutation.

But, in order to find the permutation of the smaller two element arrays, we pull out each element, compute the permutation of that smaller array of one element, add the element pulled out the the beginning of each of those permutations, and return each of those two element arrays up the recursion call stack so the original third element can be added to the beginning of that permutation and returned up the stack.

But, in order to find the permutation of the smaller one element array, we pull out the element and compute the permutation of that empty array, which just returns, and we in turn just return our one element back up the stack so the original second element can be added to the beginning of that permutation and returned up the stack.

Details

Let's note some of the steps in this function:

var permArr = [],
usedChars = [];

function permute(input) {
  var i, ch;
  for (i = 0; i < input.length; i++) {     //   loop over all elements 
    ch = input.splice(i, 1)[0];            //1. pull out each element in turn
    usedChars.push(ch);                    //   push this element
    if (input.length == 0) {               //2. if input is empty, we pushed every element
        permArr.push(usedChars.slice());   //   so add it as a permutation
    } 
    permute(input);                        //3. compute the permutation of the smaller array
    input.splice(i, 0, ch);                //4. add the original element to the beginning 
                                           //   making input the same size as when we started
                                           //   but in a different order
    usedChars.pop();                       //5. remove the element we pushed
  }
  return permArr                           //return, but this only matters in the last call
};

Let's trace through the details using the array [4,3,2,1].

When it's first passed in, we'll take out the 4, push it to usedChars, remove it from input, and call permute on [3,2,1]. In this call, we'll push 3 to usedChars, remove it from input, and call permute on [2,1]. Then we push 2 to usedChars, remove it from input, and callpermuteon [1]. Then we push 1 tousedChars, and remove it frominput`.

This leaves us four calls deep and at step (2) with: ch=1 input=[] usedChars=[4,3,2,1]

At step (2), we're going to push our first permutation [4,3,2,1] to permArr. Then, moving on, since input is now empty the recursive call in (3) will simply return and in (4) we will simply add 1 back into input and remove 1 from usedChars--and this call returns.

So, at this point, we have started backing up our recursive calls and sit at step (4) with: ch=2 input=[1] usedChars=[4,3,2]

Step (4) will perform the critical step of the algorithm: the moving action. It takes ch=2 and adds it to the beginning of input and removes it from usedChars. This means that after step (5), we have:
ch=2 input=[2,1] usedChars=[4,3]

Now take a look at where we are. We pushed [4,3,2,1] as a permutation, then backed up and swapped 2 and 1, and now we're going to go back into recursive calls to build [4,3,1,2] and add it as a permutation. After that we will back out some more, move around some more elements, and go back into the permutations and add them.

Getting back into it, after step (5) is executed we loop. That means we will push 1 to usedChars and make a recursive call with input=[2]. That call will push 2 into usedChars creating a the full array [4,3,1,2] and causing it to be added to permArray.

So, you're going to cycle up and down through the recursive calls building up a permutation, backing back out, rebuilding a different permutation, and backing out until you've looped over every possible combination.

I hope this helps!