learningjavascriptks learningjavascriptks - 2 months ago 8
Javascript Question

Recursion in a loop?

I have been trying to understand Heap's Algorithm, for days, I still cannot wrap this in my head, something just feels wrong in this code of recursion within the loop. This is a Javascript version from recursion version in Heap's algorithm at Wikipedia.

function permAlone(string) {

var x = string.split(''); // Turns the input string into a letter array.

var arr = x; // this is global, I did this so i can see elements being swapped on swap function

function swap(a, b) { // This function will simply swap positions a and b inside the input array.
debugger;
var le = arr[a]; // element a
var lf = arr[b]; // element b

var tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;

var yt = arr; // only did this to see updated elements on the array
}

var permutations = []; //output
function gen(length) {
if (length === 1) { // if true,

var x = arr.join('');

permutations.push(x); // push the updated joined' array

} else {

for (var i = 0; i < length; i++) { loop length = current elements
debugger;
gen(length - 1); // invoke recursion

swap(length % 2 ? 0 : i, length - 1); //invoke swap function. length % 2 ? 0 : i <- ternary test for the lengths' call stack. length -1 for the last element
}

}
}

gen(arr.length);
return permutations;
}


permAlone('abcd'); // this outputs to ["abcd", "bacd", "cabd", "acbd", "bcad", "cbad", "dbca", "bdca", "cdba", "dcba", "bcda", "cbda", "dacb", "adcb", "cdab", "dcab", "acdb", "cadb", "dabc", "adbc", "bdac", "dbac", "abdc", "badc"]


At first look on this code, I thought it was understandable, I understand it swaps the variable 'i'th value in the loop and the last element if it is even, then, If it's odd it swap the first and last value.. but when I saw the output, isn't the Recursion.. Recurring too much? Can someone please tell me why?

Answer

Basic idea is, given n characters:

  1. Repeatedly move (swap) a different character to the end
  2. With that character at the end, generate all permutations of the other n - 1

In general, to wrap your mind around recursion, it can be very helpful to think of the recursive call as though it were calling some other function to accomplish the task at hand. So, instead of the recursive call, to gen, "pretend" that you have some other function, say gen2, that you call:

gen2(length-1);

Think of gen2 as a black box. You don't care how it does what it does, but you know that if it generates all permutations of all of the characters except the last one, then you know that the gen algorithm will produce the correct result.

Now, if you were to write gen2, what algorithm would you use to do that? Well, how about the same algorithm you already have for gen, except that now gen2would need to have it's own black box, say gen3. How do you implement gen3? Use the same trick again, etc.

What you will find is that all of these algorithms are the same, so you can just go back to the gen algorithm where you call gen2, make a recursive call to gen instead, and throw away all the redundant methods.

Manually tracing the execution of a non-trivial recursive algorithm can be confusing because the depth of the call stack is always changing: increases, then decreases, then increases again, etc. I think this is what you are talking about in your comments. Here is a visual representation, using indentation to show the depth of the call stack.

gen(4)
   gen(3)  i = 0
      gen(2)  i = 0 
         gen(1)  i = 0
         gen(1)  i = 1
      gen(2)  i = 1 
         gen(1)  i = 0
         gen(1)  i = 1
      gen(2)  i = 2
         gen(1)  i = 0
         gen(1)  i = 1
   gen(3)  i = 1  
      gen(2)  i = 0
         gen(1)  i = 0
         gen(1)  i = 1
      gen(2)  i = 1
         gen(1)  i = 0
         gen(1)  i = 1
      gen(2)  i = 2    
         gen(1)  i = 0
         gen(1)  i = 1
  gen(3)  i = 2
      gen(2)  i = 0
         gen(1)  i = 0
         gen(1)  i = 1
      gen(2)  i = 1
         gen(1)  i = 0
         gen(1)  i = 1
      gen(2)  i = 2  
         gen(1)  i = 0
         gen(1)  i = 1          
  gen(3)  i = 3
      gen(2)  i = 0
         gen(1)  i = 0
         gen(1)  i = 1 
      gen(2)  i = 1
         gen(1)  i = 0
         gen(1)  i = 1
      gen(2)  i = 2  
         gen(1)  i = 0
         gen(1)  i = 1          

Instead of using the debugger to step through execution, you might find it helpful to add some code to print the output shown above, by adding a second parameter to gen for the stack depth:

gen(length, depth)

For your initial call, do this:

gen(arr.length, 0)

And for each recursive call:

gen(length, depth+1)

I'll leave it to you to figure out how to print the appropriate number of spaces based on the value of depth.

Comments