Trying to convert a nested loop into a recursive function

Question

I am trying to create a recursive version of the following nested loops and get the same results as the reference code. An example is below.

This is a version on Codepen http://codepen.io/anon/pen/XbQMLv

(The purpose of the code is to derive only unique combinations of integers from indices.)

Source code and output:

var len = 4; for (var a = 0; a < len; a++) { for (var b = a + 1; b < len; b++) { for (var c = b + 1; c < len; c++) { console.log(a, b, c); } } } // Outputs: // 0 1 2 // 0 1 3 // 0 2 3 // 1 2 3 

Recursive code and output:

 var len = 4; var end = 3; var data = []; var loop = function (index) { if (index === end) { console.log(data); return; } for (var i = index; i < len; i++) { data[index] = i; loop(i + 1); } } loop(0); // Outputs: // [ 0, 1, 2 ] // [ 0, 2, 3 ] // [ 1, 3, 2 ] // [ 2, 3, 3 ] 

Not sure what I'm missing here.

Answer 1

There is a small error in your code:

You are calling a recursive function from your i + 1 , but not your index + 1 .
This makes index not equal to the current index of the array, but to the value.

For example, when you passed [0, 1, 2] , your data is now [0, 1] , and you are going to insert 3 , you call loop(3 + 1) , index 4 goes out of the range of arrays. if (index === end) condition is not satisfied, and it is not displayed. for (var i = index; i < len; i++) does not work, and everything goes wrong.

It should be:

 var len = 4; var end = 3; var data = []; var loop = function (index) { if (index === end) { console.log(data); return; } for (var i = index; i < len; i++) { data[index] = i; loop(index + 1); // <--- HERE } } loop(0); 

Here is a working demo of JSFiddle .

Update:

Oh, now I see. For all combinations, you need the condition a[i] > a[i-1] . Just add a start variable that will keep the last inserted value to match this rule.

 var len = 4; var end = 3; var data = []; var loop = function (start, index) { if (index === end) { document.body.innerHTML += "<br/>" + data; return; } for (var i = start; i < len; i++) { // We start from 'start' (the last value + 1) data[index] = i; loop(i + 1, index + 1); // Here, we pass the last inserted value + 1 } } loop(0, 0); // At beginning, we start from 0 

Updated JSFiddle demo with passing argument .

You can check the previous value instead of passing the value as an argument if it looks wrong to you. The condition will look like this: "if this is the first number, start at 0; else - start at the next number after the previous one."

 var start = (index === 0 ? 0 : data[index-1] + 1); 

Updated JSFiddle demonstration with the start of calculation .

Answer 2

Since you have three for loops, one inside the other, you must pass 2 arguments for the recursion function.

 var len = 4; var end = 3; var data = []; var loop = function(start, index) { if (index === end) { console.log(data); return; } for (var i = start; i < len; i++) { data[index] = i; loop(i + 1, index + 1); //Pass as like a+1 & b+1 } } loop(0, 0); 

Answer 3

There are a few mistakes; you start with i+1 instead of index+1 , and you count from index instead of counting from data[index-1]+1 .

The corrected version:

 var len = 4; var end = 3; var data = []; var loop = function (index) { if (index === end) { console.log(data); return; } for (var i = (index==0 ? 0 : data[index-1]+1); i < len; i++) { data[index] = i; loop(index + 1); } } 

Answer 4

Print the exact expected result.

 var len = 4; var end = 3; var data = []; var loop = function(i) { if(data.length === end) { // console.log(data); -> Wont work in snippet // Snippet workaround document.getElementsByTagName('body')[0].innerHTML += data.join(',') + '<br/>'; return; } if(i >= len) return; data.push(i); loop(i + 1); data.pop(); loop(i + 1); }; loop(0);