AlanH AlanH - 4 months ago 12
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

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' ]