AlanH - 1 year ago 68
Javascript Question

# Need help understanding recursive function to generate all combinations of a string

I came across this code, but am having a hard time figuring out how the flow of this function is working.

``````function combinations(str) {
var fn = function(active, rest, a) {
if (!active && !rest)
return;
if (!rest) {
a.push(active);
} else {
fn(active + rest[0], rest.slice(1), a);
fn(active, rest.slice(1), a);
}
return a;
}
return fn("", str, []);
}
``````

I've console.logged a bunch of statements, but I'm getting lost in the recursion. Specifically, I don't understand what's happening after the first of the two
`fn`
's gets returned. It's simply returning
`a`
, but to me, it appears as if the second
`fn`
knows to take the returned
`a`
. How does that work? Shouldn't it need a variable assignment like so:

``````a = fn(active + rest[0], rest.slice(1), a);
fn(active, rest.slice(1), a);
``````

Answer Source

Well, if you're trying to understand the specific algorithm, the key insight is the `a` variable accumulates the result by reference -- the lower level calls to `combinations()` push individual elements onto `a` and the function eventually returns accumulated result.

A good print statement can help understanding cases like this. Here's the code with the addition of a print out that shows you what level of recursion you're at. And I renamed `a` to `accum` to make it a bit more obvious:

``````function combinations(str) {
var fn = function(active, rest, accum, level) {
console.log(new Array(level).join('--'),
' active: \'' + active + '\'',
'rest: \'' + rest + '\'',
'accum:', accum);
if (!active && !rest)
return;
if (!rest) {
accum.push(active);
} else {
fn(active + rest[0], rest.slice(1), accum, level + 1);
fn(active, rest.slice(1), accum, level + 1);
}
return accum;
}
return fn("", str, [], 1);
}
``````

and the results:

``````combinations('abc')
active: '' rest: 'abc' accum: []
--  active: 'a' rest: 'bc' accum: []
----  active: 'ab' rest: 'c' accum: []
------  active: 'abc' rest: '' accum: []
------  active: 'ab' rest: '' accum: [ 'abc' ]
----  active: 'a' rest: 'c' accum: [ 'abc', 'ab' ]
------  active: 'ac' rest: '' accum: [ 'abc', 'ab' ]
------  active: 'a' rest: '' accum: [ 'abc', 'ab', 'ac' ]
--  active: '' rest: 'bc' accum: [ 'abc', 'ab', 'ac', 'a' ]
----  active: 'b' rest: 'c' accum: [ 'abc', 'ab', 'ac', 'a' ]
------  active: 'bc' rest: '' accum: [ 'abc', 'ab', 'ac', 'a' ]
------  active: 'b' rest: '' accum: [ 'abc', 'ab', 'ac', 'a', 'bc' ]
----  active: '' rest: 'c' accum: [ 'abc', 'ab', 'ac', 'a', 'bc', 'b' ]
------  active: 'c' rest: '' accum: [ 'abc', 'ab', 'ac', 'a', 'bc', 'b' ]
------  active: '' rest: '' accum: [ 'abc', 'ab', 'ac', 'a', 'bc', 'b', 'c' ]
[ 'abc', 'ab', 'ac', 'a', 'bc', 'b', 'c' ]
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download