Recursion in a loop?

Question

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?

Is the code your own implementation or on the wiki page? I cannot find the code snippet on the link in your OP — shole
– shole, Commented Sep 14, 2016 at 4:15
Are you having difficulty with the idea behind the algorithm, or the recursion? — Joel Lee
– Joel Lee, Commented Sep 14, 2016 at 4:16
@shole , i extracted the heap algorithms' part, but it's here link , — learningjavascriptks
– learningjavascriptks, Commented Sep 14, 2016 at 4:20
@JoelLee I get the algorithm but not the recursion part in the loop, why is it recurring the way it is recurring? :( — learningjavascriptks
– learningjavascriptks, Commented Sep 14, 2016 at 4:24

Hin Fan Chan · Accepted Answer · 2016-09-14 04:32:34Z

2

It isn't too much. For n elements, the number of permutation is n!. In your case, it is 4!, which is 4*3*2*1 = 24. Since the function gen pushes an element into the array permutations each time it gets called, you know it gets called exactly 24 times as there are 24 elements in the array.

Note that the permutation of n elements is

the 1st element + all permutations of the rest of the elements (n-1) plus

the 2nd element + all permutations of the rest of the elements (n-1) plus

...

the nth element + all permutations of the rest of the elements (n-1)

So the number of elements p(n) = n * p(n-1). Looking this p(n), you can see why there is a recursion within a loop.

answered Sep 14, 2016 at 4:32

Hin Fan Chan

1,65311 silver badges11 bronze badges

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

2 Comments

Joel Lee Over a year ago

Correct analysis of number of calls.

learningjavascriptks Over a year ago

I am still introducing my self in Js, this is the first time that I encounter this kind of code, I would like to accept your answer but I still feel something's wrong @JoelLee can you please clarify this

Joel Lee · Accepted Answer · 2016-09-14 17:02:54Z

Basic idea is, given n characters:

Repeatedly move (swap) a different character to the end
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.

Thanks! cleared my confusion, I thought it was still looping after -1, I was even wondering why after the push on call stack 1 it's in stack 2s' swap function.

Kevin Le - Khnle · Accepted Answer · 2016-09-14 04:37:57Z

0

Not sure what you're trying to ask. The explanation of the algorithm is already given in the wikipedia article. Not sure if any effort can better that. But if the question is about the implementation then I think it can be implemented as follow:

function swap(arr, a, b) {
  var tmp = arr[a];
  arr[a] = arr[b];
  arr[b] = tmp;

  return arr;
}

function generate(n, arr) {
  if (n === 1) {
    console.log(arr);
  } else {
    for (var i = 0; i < n - 1; i = i + 1) {
      generate(n - 1, arr);
      if (n % 2 === 0) {
        arr = swap(arr, i, n-1);
      } else {
        arr = swap(arr, 0, n-1);
      }
    }
    generate(n - 1, arr);
  }
}

let arr = ['a', 'b', 'c', 'd'];
arr = generate(4, arr);

http://jsbin.com/xigekoy/edit?js,console

edited Sep 14, 2016 at 4:37

answered Sep 14, 2016 at 4:32

Kevin Le - Khnle

10.9k11 gold badges57 silver badges85 bronze badges

Collectives™ on Stack Overflow

Recursion in a loop?

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related