I want to convert this nested loops in recursion. How do I achieve this?

for(let i = 0; i < 5; i++) {
  for(let j = 0; j < 5; j++) {
    console.log(i,j);
  }
}

I want to convert this nested loops in recursion. How do I achieve this?

for(let i = 0; i < 5; i++) {
  for(let j = 0; j < 5; j++) {
    console.log(i,j);
  }
}

• javascript
• loops
• recursion

• 1 why? you wont even safe a line of code – Jonas Wilms Commented Mar 17, 2018 at 21:08
• I'm learning recursion so want to get more clear. – Dhruv Commented Mar 17, 2018 at 21:10
• 1 So many answers but no accepted or up voted.... – Endless Commented Mar 17, 2018 at 22:12
• @Endless, take one which is most versatile or what ever you like. – Nina Scholz Commented Mar 17, 2018 at 22:20
• should not e from me but Dhruv – Endless Commented Mar 17, 2018 at 23:20

10 Answers 10

Here another example of this recursion:

function loop(i,j,limitI,limitJ){
     if(i>=limitI) return;
     if(j>=limitJ) loop(i+1,0,limitI,limitJ);
     else{
       console.log(i,j);
       loop(i,j+1,limitI,limitJ)
     }
 }
loop(0,0,4,4);

Generic function product calculates the Cartesian product of its inputs - You can polyfill Array.prototype.flatMap if it's not already in your environment

Array.prototype.flatMap = function (f, context)
{
  return this.reduce ((acc, x) => acc.concat (f (x)), [])
}

const product = (first = [], ...rest) =>
{
  const loop = (b, first, ...rest) =>
    rest.length === 0
      ? first.map (x => [ ...b, x ])
      : first.flatMap (x => loop ([ ...b, x ], ...rest))
  return loop ([], first, ...rest)
}

const suits =
  ['♤', '♡', '♧', '♢']

const ranks =
  ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']

for (const card of product (ranks, suits))
  console.log (card)

// [ 'A', '♤' ]
// [ 'A', '♡' ]
// [ 'A', '♧' ]
// [ 'A', '♢' ]
// [ '2', '♤' ]
// ...
// [ 'Q', '♧' ]
// [ 'K', '♤' ]
// [ 'K', '♡' ]
// [ 'K', '♧' ]
// [ 'K', '♢' ]

product is a variadic function (by use of a rest parameter) which accepts 1 or more inputs

const range = (min = 0, max = 0) =>
  max < min
    ? []
    : [ min, ...range (min + 1, max) ]

const r =
  range (0, 2)

for (const b of product (r, r, r))
  console.log (b)

// [ 0, 0, 0 ]
// [ 0, 0, 1 ]
// [ 0, 0, 2 ]
// [ 0, 1, 0 ]
// ...
// [ 2, 1, 2 ]
// [ 2, 2, 0 ]
// [ 2, 2, 1 ]
// [ 2, 2, 2 ]

Using destructuring assignment, you can effectively create nested loops

for (const [ i, j ] of product (range (0, 5), range (0, 5)))
  console.log ("i %d, j %d", i, j)

// i 0, j 0
// i 0, j 1
// i 0, j 2
// i 0, j 3
// i 0, j 4
// i 0, j 5
// i 1, j 0
// ...
// i 4, j 5
// i 5, j 0
// i 5, j 1
// i 5, j 2
// i 5, j 3
// i 5, j 4
// i 5, j 5

product can also be written using generators - below, we find all perfect Pythagorean triples under 20

const product = function* (first, ...rest)
{
  const loop = function* (b, first, ...rest)
  {
    if (rest.length === 0)
      for (const x of first)
        yield [ ...b, x ]
    else
      for (const x of first)
        yield* loop ([ ...b, x ], ...rest)
  }
  yield* loop ([], first, ...rest)
}

const range = (min = 0, max = 0) =>
  max < min
    ? []
    : [ min, ...range (min + 1, max) ]

const pythagTriple = (x, y, z) =>
  (x * x) + (y * y) === (z * z)

const solver = function* (max = 20)
{
  const N = range (1, max)
  for (const [ x, y, z ] of product (N, N, N))
    if (pythagTriple (x, y, z))
      yield [ x, y, z ]
}

console.log ('solutions:', Array.from (solver (20)))

// solutions:
// [ [ 3, 4, 5 ]
// , [ 4, 3, 5 ]
// , [ 5, 12, 13 ]
// , [ 6, 8, 10 ]
// , [ 8, 6, 10 ]
// , [ 8, 15, 17 ]
// , [ 9, 12, 15 ]
// , [ 12, 5, 13 ]
// , [ 12, 9, 15 ]
// , [ 12, 16, 20 ]
// , [ 15, 8, 17 ]
// , [ 16, 12, 20 ]
// ]

I think using map (and reduce), while it allows for more plex recursive structures as you demonstrate, is actually an implicit for loop, which does not really answer the question on how to convert one into a recurrence. However, if you also defined a recursive map and reduce, then it would be OK :) - גלעד ברקן

Your wish is my mand :D

const Empty =
  Symbol ()

const concat = (xs, ys) =>
  xs.concat (ys)
  
const append = (xs, x) =>
  concat (xs, [ x ])

const reduce = (f, acc = null, [ x = Empty, ...xs ]) =>
  x === Empty
    ? acc
    : reduce (f, f (acc, x), xs)

const mapReduce = (m, r) =>
  (acc, x) => r (acc, m (x))
    
const map = (f, xs = []) =>
  reduce (mapReduce (f, append), [], xs)
  
const flatMap = (f, xs = []) =>
  reduce (mapReduce (f, concat), [], xs)

const product = (first = [], ...rest) =>
{
  const loop = (b, first, ...rest) =>
    rest.length === 0
      ? map (x => append (b, x), first)
      : flatMap (x => loop (append (b, x), ...rest), first)
  return loop ([], first, ...rest)
}

const suits =
  ['♤', '♡', '♧', '♢']

const ranks =
  ['A', '2', '3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K']

for (const card of product (ranks, suits))
  console.log (card)

// same output as above

I don't remend this but you can do following(as it is difficult to read, for readability and understandability your code is best).

function forLoop(i,j){
    if(j===0){
        if(i!==0)
          forLoop(i-1,4);
        console.log(i,j);
    }
    else{
        forLoop(i,j-1);
        console.log(i,j);
    }
}

forLoop(4,4);  

Here's my rendition:

  function nested(i, j, maxI, maxJ) {
    if (i == maxI) return

    console.log(i, j)

    if (i < maxI) {
      ++j < maxJ ? nested(i, j, maxI, maxJ) : nested(++i, 0, maxI, maxJ)
    }
  }
  
  nested(0, 0, 5, 5)

This is an alternative.

This approach uses param initialization with ma operator (just to make the code shorter).

Additionally, an operator param (callback) to execute any logic for each iteration.

function loop(n, operator, i = 0, j = 0) { // Param initialization.
  if (j === n) (j = 0, i++); // Comma operator.
  if (i === n) return;

  operator(i, j);

  loop(n, operator, i, ++j);
}

loop(5, (i, j) => console.log(i, j));

.as-console-wrapper { max-height: 100% !important; top: 0; }

You could use an array for limit and values. The order is reversed, because of the incrementing of the lowest index first.

This works for an arbitrary count of nested loops and it allowes to use an arbitrary limit of the max values.

function iter(limit, values = limit.map(_ => 0)) {
    console.log(values.join(' '));
    values = values.reduce((r, v, i) => {
        r[i] = (r[i] || 0) + v;
        if (r[i] >= limit[i]) {
            r[i] = 0;
            r[i + 1] = (r[i + 1] || 0) + 1;
        }
        return r;
    }, [1]);
    if (values.length > limit.length) {
        return;
    }
    iter(limit, values);
}

iter([2, 3]);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Here's an outline of a "recurrence relation," where "each further term of the sequence ... is defined as a function of the preceding terms."

As you are probably aware, recursive functions usually have at least one base case, terminating the recursion, and at least one recursive call. To find a pattern, let's examine the sequence:

0,0
0,1
0,2
0,3
0,4
1,0
1,2
...

Our base case, where the call to a preceding parameter terminates, seems to be 0,0. But this is also where the console logs begin, which means we first have to call all the way back to the base case. For convenience, let's assume the function expects positive parameters:

function f(i, j){
  if (i == 0 && j == 0){
    console.log(i,j);
    return;
  }
}

We can also notice that the outer loop, the i, stays constant for each cycle of js:

function f(i, j){
  if (i == 0 && j == 0){
    console.log(i,j);
    return;
  }

  if (j == 0)
  // ... what happens here?
}

but here we get stuck. When j is greater than zero, we can determine that the current term came from f(i, j - 1), but if j is zero in the current term, we have no way of formulating what it was in the preceding term. We need one more parameter:

function f(i, j, jj){
  if (i == 0 && j == 0){
    console.log(i,j);
    return;
  }

  if (j == 0)
    f(i - 1, jj, jj);
  else
    f(i, j - 1, jj);
  
  console.log(i,j);
}

f(4,4,4);

You could recurse by taking a depth and the values to iterate:

 function loop(start, end, depth, exit, ...args){
   for(let i = start; i < end; i++)
     depth ? loop(start, end, depth - 1, exit, ...args, i) : exit(...args, i);
 }

Usable as:

 loop(0, 5, 1, (i, j) => console.log(i, j))

The only real usecase would be deeper loops, e.g. this one

If you want it pletely without for:

  const range = (start, end, cb) =>
     (cb(start), start + 1 >= end || range (start + 1, end, cb));


 function loop(start, end, depth, exit, ...args){
   range(start, end, i => 
     depth ? loop(start, end, depth - 1, exit, ...args, i) : exit(...args, i));
 }

Try it

Transforming a nested for loop into its recursive counterpart is surprisingly hard. Good question!

You can transform every loop (without a stack) into a tail recursive algorithm. So this rule should hold for a nested loop too.

I think we need two distinct functions to get something equivalent to your two nested loops:

const loop = ([i, j], [k, l]) => {
  const loop_ = (k_, l_) => {
    if (k_ >= l_) return;

    else {
      console.log(i, k_);
      loop_(k_ + 1, l_);
    }
  };

  if (i >= j) return;

  else {
    loop_(k, l);
    loop([i + 1, j], [k, l]);
  }
};

loop([0, 5], [0, 5]);

You have to pass ranges for both the out and the inner loop.

As you can see both recursive calls are in tail position. I think this is the closest equivalent we can get.

suggested solution

function recurse(arg1=0, arg2=0, cb) {

    if ( arg2 <= 5 ) {

        let _l = arg2++;

        if ( arg1 === 5 )
            return ;

        if ( ++_l === 6 ) {
            arg2 = 0;
            cb(arg1++, arg2);
            recurse(arg1, arg2, cb);
        } else {
            cb(arg1, arg2 - 1);
            recurse(arg1, arg2, cb);
        }

    }
}

recurse( 0 , 0 , (i,j) => console.log(i,j));