learningjavascriptks - 1 year ago 48
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;
}

``````

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?

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 `gen2`would 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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download