javascript recursive parameter behavior

Question

I want to list all the possible parameter combinations. I wrote a recursive algorithm that should solve the problem. The issue is that the variables I use as the recurive parameters does not keep their old values before the recursive calls.

The problem

Let's say I have 2 parameters with the following possible values:

P1 = A or B
P2 = C or D or E

I want to find the possible combinations:

AC
AD
AE
BC
BD
BE

The recursive "solution"

var params = [];

var param1 = ['A', 'B', 'C'];
var param2 = ['E', 'F'];
var param3 = ['G', 'H', 'I'];

params.push(param1);
params.push(param2);
params.push(param3);

function r(ps, s) {
    console.log(ps.length + " " + s.length);
    if (ps.length == 0) {
        console.log(s);
        return;
    }
    var p = ps[0];
    for (idx in p) {
        s.push(p[idx]);
        console.log("Before call " + s);
        r(ps.slice(1), s);
    }
}

var sol = [];
r(params, sol);

JS Fiddle

The runtime issue

When running the program, the s variable keeps growing. The first 3 iterations gives:

Before call A
Before call A, E
Before call A, E, G

After the first call to return, I expect the s variable to contain AE because it was its value before the call.

Note: what you want is the [Cartesian Product](http://en.wikipedia.org/wiki/Cartesian_product) of your values. I have a question about this with excellent JavaScript answers here: http://stackoverflow.com/questions/9422386/lazy-cartesian-product-of-arrays-arbitrary-nested-loops See also the links in the opening sentence for other non-lazy JavaScript versions. — Phrogz, Dec 14 '14 at 16:09

cyon · Accepted Answer · 2014-12-14T19:51:40.890

To fix your algorithm you need to pop the element from the array when you return from the recursive call:

for (idx in p) {
    s.push(p[idx]);
    r(ps.slice(1), s);
    s.pop(); // remove the element once we are done with the recursion
}

Note however, that console.log(s) will show the reference to the object which means that in the console you will see the s empty because the algorithm will complete quickly and after it's done s becomes empty because of the popping. To force console.log to print the contents and not the reference you can use console.log(s.toString()):

if (ps.length == 0) {
    console.log(s.toString());
    return;
}

javascript recursive parameter behavior

1 Answers1