How to convert nested loop in to recursion?

Question

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);
  }
}

Answer 1

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 = (comb, first, ...rest) =>
    rest.length === 0
      ? first.map (x => [ ...comb, x ])
      : first.flatMap (x => loop ([ ...comb, 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 comb of product (r, r, r))
  console.log (comb)

// [ 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* (comb, first, ...rest)
  {
    if (rest.length === 0)
      for (const x of first)
        yield [ ...comb, x ]
    else
      for (const x of first)
        yield* loop ([ ...comb, 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 complex 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 command :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 = (comb, first, ...rest) =>
    rest.length === 0
      ? map (x => append (comb, x), first)
      : flatMap (x => loop (append (comb, 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

Answer 2

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.

Answer 3

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 completely 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

Answer 4

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);

Answer 5

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; }

Answer 6

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);

Answer 7

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));

Answer 8

This is an alternative.

This approach uses param initialization with comma 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; }

Answer 9

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)

Answer 10

I don't recommend 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);