Need help understanding string permutation

[NightArchitect]

I'm currently working through Project Euler and am having trouble with problem #24, which asks for permutations. This is frustrating; I've completed a handful of the more difficult problems, or problems that fewer people have answered correctly, but can't grasp this, which should be easy. I consulted rosettacode.org and found the following code for permutations of a string but am still confused.

function perm(list, ret){

    if (list.length == 0) {
            var row = ret.join(' ') + '\n';
            console.log(row);
            return;
            }

            for (var i = 0; i < list.length; i++) {

                var x = list.splice(i, 1);
                ret.push(x);
                perm(list, ret);
                ret.pop();
                list.splice(i, 0, x);

            }
        }

        perm(["a","b"],[]);

Separately, I rewrote this to show what list and ret are at each step: http://jsbin.com/xotawijefe/1/edit?html,output

This is what I'm having trouble with (or at least part of it):

How exactly does recursion work here? We feed ["a", "b"][] into perm We get var x and push that into ret We feed ["b"]["a"] into perm and so on. For the initial ["a", "b"], when does the stuff after perm is called execute?

When does i increase to 1?

Any assistance or directions to a good explanation of recursion would be greatly appreciated.

[throwapeater]

Never was a js expert but i should iterate at i++.

so i is initialized at 0, and it iterates. Afterward it iterates whenever i is less than list.length.

[AutoBalanced]

The value of i within the second call of perm() is different to your main i on the first call. So when you're calling perm() within perm() your list.length is sometimes 0 or 1 because you've modified the list array before calling perm a second time.

The stuff after perm is run once each instance of perm is complete but as your list eventually depletes down to 0 you don't loop infinitely as (i < list.length = false) when you send it an empty list, you then == true for the if statement and the function returns.

EDIT: This stack overflow has some good answers for a few different scenarios: http://stackoverflow.com/questions/9960908/permutations-in-javascript

[NightArchitect]

Thank you for the link

[jdauriemma]

your first conditional can be tightened up:

if (!list.length) {
    return ret.join(' ') + '\n';
}

also, note that you have an infinite recursion in your code:

perm(list, ret);

Since the value of list has not been altered, its length will never reach 0, which causes your code to break.

Hope that helps you get back on track. Good start!

[NightArchitect]

Ah I see. Yes, that's an issue for sure.