How do I replace for loops with recursion in Javascript?

Question

I have 2 for loops that work well to create a grid with rows and columns, but I would like to improve the solution using recursion as it is more cleaner and recommended (in Functional Programming).

The desired output is a single array of pairs used in css grid

const createGrid = (rows,columns) => {
    let grid=[]
    for (let y = 3; y <= rows; y += 2){
        let row = []
        for (let x = 3; x <= columns; x += 2){
            let col = [y, x]
            row = [...row,col]
        }
        grid =[...grid, ...row]
    }
    return grid
}

Are there also any guidelines as to how to convert for loops to recursion solutions when possible?

Answer 1

primitive recursion

Here's one possible way to make a grid using recursion -

const makeGrid = (f, rows = 0, cols = 0) =>
  rows <= 0
    ? []
    : [ ...makeGrid(f, rows - 1, cols), makeRow(f, rows, cols) ]

const makeRow = (f, row = 0, cols = 0) =>
  cols <= 0
    ? []
    : [ ...makeRow(f, row, cols - 1), f(row, cols) ]

const g =
  makeGrid((x, y) => ({ xPos: x, yPos: y }), 2, 3)

console.log(JSON.stringify(g))
// [ [ {"xPos":1,"yPos":1}
//   , {"xPos":1,"yPos":2}
//   , {"xPos":1,"yPos":3}
//   ]
// , [ {"xPos":2,"yPos":1}
//   , {"xPos":2,"yPos":2}
//   , {"xPos":2,"yPos":3}
//   ]
// ]

The functional param f allows us to construct grid cells in a variety of ways

const g =
  makeGrid((x, y) => [ x - 1, y - 1 ], 3, 2)

console.log(JSON.stringify(g))
// [ [ [ 0, 0 ]
//   , [ 0, 1 ]
//   ]
// , [ [ 1, 0 ]
//   , [ 1, 1 ]
//   ]
// , [ [ 2, 0 ]
//   , [ 2, 1 ]
//   ]
// ]

---

work smarter, not harder

Per Bergi's comment, you can reduce some extra argument passing by using a curried cell constructor -

const makeGrid = (f, rows = 0, cols = 0) =>
  rows <= 0
    ? []
    : [ ...makeGrid(f, rows - 1, cols), makeRow(f(rows), cols) ]

const makeRow = (f, cols = 0) =>
  cols <= 0
    ? []
    : [ ...makeRow(f, cols - 1), f(cols) ]

const g =
  makeGrid
    ( x => y => [ x, y ] // "curried" constructor
    , 2
    , 3
    )

console.log(JSON.stringify(g))
// [ [ [ 1, 1 ]
//   , [ 1, 2 ]
//   , [ 1, 3 ]
//   ]
// , [ [ 2, 1 ]
//   , [ 2, 2 ]
//   , [ 2, 3 ]
//   ]
// ]

have your cake and eat it too

Alternatively, we can incorporate the suggestion and still accept a binary function at the call site using partial application -

const makeGrid = (f, rows = 0, cols = 0) =>
  rows <= 0
    ? []
    : [ ...makeGrid(f, rows - 1, cols)
      , makeRow(_ => f(rows, _), cols) // <-- partially apply f
      ]

const makeRow = (f, cols = 0) =>
  cols <= 0
    ? []
    : [ ...makeRow(f, cols - 1), f(cols) ]

const g =
  makeGrid
    ( (x,y) => [ x, y ] // ordinary constructor
    , 2
    , 3
    )

console.log(JSON.stringify(g))
// [ [ [ 1, 1 ]
//   , [ 1, 2 ]
//   , [ 1, 3 ]
//   ]
// , [ [ 2, 1 ]
//   , [ 2, 2 ]
//   , [ 2, 3 ]
//   ]
// ]

---

Nth dimension

Above we are limited to 2-dimensional grids. What if we wanted 3-dimensions or even more?

const identity = x =>
  x

const range = (start = 0, end = 0) =>
  start >= end
    ? []
    : [ start, ...range(start + 1, end) ] // <-- recursion

const map = ([ x, ...more ], f = identity) =>
  x === undefined
    ? []
    : [ f(x), ...map(more, f) ] // <-- recursion

const makeGrid = (r = [], d = 0, ...more) =>
  d === 0
    ? r
    : map(range(0, d), x => makeGrid(r(x), ...more)) // <-- recursion

const g =
  makeGrid
    ( x => y => z => [ x, y, z ] // <-- constructor
    , 2       // <-- dimension 1
    , 2       // <-- dimension 2
    , 3       // <-- dimension 3
    , // ...     <-- dimension N
    )

console.log(JSON.stringify(g))

Output

[ [ [ [0,0,0]
    , [0,0,1]
    , [0,0,2]
    ]
  , [ [0,1,0]
    , [0,1,1]
    , [0,1,2]
    ]
  ]
, [ [ [1,0,0]
    , [1,0,1]
    , [1,0,2]
    ]
  , [ [1,1,0]
    , [1,1,1]
    , [1,1,2]
    ]
  ]
]

---

any dimensions; flat result

Per you comment, you want a flat array of pairs. You can achieve that by simply substituting map for flatMap, as demonstrated below -

const identity = x =>
  x

const range = (start = 0, end = 0) =>
  start >= end
    ? []
    : [ start, ...range(start + 1, end) ]

const flatMap = ([ x, ...more ], f = identity) =>
  x === undefined
    ? []
    : [ ...f(x), ...flatMap(more, f) ] // <-- flat!

const makeGrid = (r = [], d = 0, ...more) =>
  d === 0
    ? r
    : flatMap(range(0, d), x => makeGrid(r(x), ...more))

const g =
  makeGrid
    ( x => y => [{ x, y }]  // <-- constructor
    , 2       // <-- dimension 1
    , 2       // <-- dimension 2
    , // ...     <-- dimension N
    )

console.log(JSON.stringify(g))
// [ { x: 0, y: 0 }
// , { x: 0, y: 1 }
// , { x: 1, y: 0 }
// , { x: 1, y: 1 }
// ]

The functional constructor demonstrates its versatility again -

const g =
  makeGrid
    ( x => y =>
        [[ 3 + x * 2, 3 + y * 2 ]] // whatever you want
    , 3
    , 3
    )

console.log(JSON.stringify(g))
// [[3,3],[3,5],[3,7],[5,3],[5,5],[5,7],[7,3],[7,5],[7,7]]

---

learn more

As other have show, this particular version of makeGrid using flatMap is effectively computing a cartesian product. By the time you've wrapped your head around flatMap, you already know the List Monad!

---

more cake, please!

If you're hungry for more, I want to give you a primer on one of my favourite topics in computational study: delimited continuations. Getting started with first class continuations involves developing an intuition on some ways in which they are used -

reset
  ( call
      ( (x, y) => [[ x, y ]]
      , amb([ 'J', 'Q', 'K', 'A' ])
      , amb([ '♡', '♢', '♤', '♧' ])
      )
  )

// [ [ J, ♡ ], [ J, ♢ ], [ J, ♤ ], [ J, ♧ ]
// , [ Q, ♡ ], [ Q, ♢ ], [ Q, ♤ ], [ Q, ♧ ]
// , [ K, ♡ ], [ K, ♢ ], [ K, ♤ ], [ K, ♧ ]
// , [ A, ♡ ], [ A, ♢ ], [ A, ♤ ], [ A, ♧ ]
// ]

Just like the List Monad, above amb encapsulates this notion of ambiguous (non-deterministic) computations. We can easily write our 2-dimensional simpleGrid using delimited continuations -

const simpleGrid = (f, dim1 = 0, dim2 = 0) =>
  reset
    ( call
        ( f
        , amb(range(0, dim1))
        , amb(range(0, dim2))
        )
    )

simpleGrid((x, y) => [[x, y]], 3, 3)
// [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

Creating an N-dimension grid is a breeze thanks to amb as well. The implementation has all but disappeared -

const always = x =>
  _ => x

const multiGrid = (f = always([]), ...dims) =>
  reset
    ( apply
        ( f
        , dims.map(_ => amb(range(0, _)))
        )
    )

multiGrid
  ( (x, y, z) => [[ x, y, z ]] // <-- not curried this time, btw
  , 3
  , 3
  , 3
  )

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

Or we can create the desired increments and offsets using line in the cell constructor -

const line = (m = 1, b = 0) =>
  x => m * x + b // <-- linear equation, y = mx + b

multiGrid
  ( (...all) => [ all.map(line(2, 3)) ] // <-- slope: 2, y-offset: 3
  , 3
  , 3
  , 3
  )

// [ [3,3,3], [3,3,5], [3,3,7]
// , [3,5,3], [3,5,5], [3,5,7]
// , [3,7,3], [3,7,5], [3,7,7]
// , [5,3,3], [5,3,5], [5,3,7]
// , [5,5,3], [5,5,5], [5,5,7]
// , [5,7,3], [5,7,5], [5,7,7]
// , [7,3,3], [7,3,5], [7,3,7]
// , [7,5,3], [7,5,5], [7,5,7]
// , [7,7,3], [7,7,5], [7,7,7]
// ]

So where do reset, call, apply, and amb come from? JavaScript does not support first class continuations, but nothing stops us from implementing them on our own -

const call = (f, ...values) =>
  ({ type: call, f, values })  //<-- ordinary object

const apply = (f, values) =>
  ({ type: call, f, values })  //<-- ordinary object

const shift = (f = identity) =>
  ({ type: shift, f })         //<-- ordinary object

const amb = (xs = []) =>
  shift(k => xs.flatMap(x => k(x))) //<-- returns ordinary object

const reset = (expr = {}) =>
  loop(() => expr)             //<-- ???

const loop = f =>
  // ...                       //<-- follow the link!

Given the context of your question, it should be obvious that this is a purely academic exercise. Scott's answer offers sound rationale on some of the trade-offs we make. Hopefully this section shows you that higher-powered computational features can easily tackle problems that initially appear complex.

First class continuations unlock powerful control flow for your programs. Have you ever wondered how JavaScript implements function* and yield? What if JavaScript didn't have these powers baked in? Read the post to see how we can make these (and more) using nothing but ordinary functions.

---

continuations code demo

See it work in your own browser! Expand the snippet below to generate grids using delimited continuations... in JavaScript! -

// identity : 'a -> 'a
const identity = x =>
  x

// always : 'a -> 'b -> 'a
const always = x =>
  _ => x

// log : (string, 'a) -> unit
const log = (label, x) =>
  console.log(label, JSON.stringify(x))
  
// line : (int, int) -> int -> int
const line = (m, b) =>
  x => m * x + b
  
// range : (int, int) -> int array
const range = (start = 0, end = 0) =>
  start >= end
    ? []
    : [ start, ...range(start + 1, end) ]

// call : (* -> 'a expr, *) -> 'a expr
const call = (f, ...values) =>
  ({ type: call, f, values })

// apply : (* -> 'a expr, * array) -> 'a expr
const apply = (f, values) =>
  ({ type: call, f, values })

// shift : ('a expr -> 'b expr) -> 'b expr
const shift = (f = identity) =>
  ({ type: shift, f })

// reset : 'a expr -> 'a
const reset = (expr = {}) =>
  loop(() => expr)

// amb : ('a array) -> ('a array) expr
const amb = (xs = []) =>
  shift(k => xs .flatMap (x => k (x)))

// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
  const aux1 = (expr = {}, k = identity) =>
  { switch (expr.type)
    { case call:
        return call(aux, expr.f, expr.values, k)
      case shift:
          return call
            ( aux1
            , expr.f(x => trampoline(aux1(x, k)))
            , identity
            )
      default:
        return call(k, expr)
    }
  }

  // aux : (* -> 'a, (* expr) array, 'a -> 'b) -> 'b
  const aux = (f, exprs = [], k) =>
  { switch (exprs.length)
    { case 0:
        return call(aux1, f(), k) // nullary continuation
      case 1:
        return call
          ( aux1
          , exprs[0]
          , x => call(aux1, f(x), k) // unary
          )
      case 2:
        return call
          ( aux1
          , exprs[0]
          , x =>
            call
              ( aux1
              , exprs[1]
              , y => call(aux1, f(x, y), k) // binary
              )
          )
      case 3: // ternary ...
      case 4: // quaternary ...
      default: // variadic
        return call
          ( exprs.reduce
              ( (mr, e) =>
                  k => call(mr, r => call(aux1, e, x => call(k, [ ...r, x ])))
              , k => call(k, [])
              )
          , values => call(aux1, f(...values), k)
          )
    }
  }

  return trampoline(aux1(f()))
}

// trampoline : * -> *
const trampoline = r =>
{ while (r && r.type === call)
    r = r.f(...r.values)
  return r
}

// simpleGrid : ((...int -> 'a), int, int) -> 'a array
const simpleGrid = (f, dim1 = 0, dim2 = 0) =>
  reset
    ( call
        ( f
        , amb(range(0, dim1))
        , amb(range(0, dim2))
        )
    )

// multiGrid : (...int -> 'a, ...int) -> 'a array
const multiGrid = (f = always([]), ...dims) =>
  reset
    ( apply
        ( f
        , dims.map(_ => amb(range(0, _)))
        )
    )

// : unit
log
  ( "simple grid:"
  , simpleGrid((x, y) => [[x, y]], 3, 3)
  )

// : unit
log
  ( "multiGrid:"
  , multiGrid
      ( (...all) => [ all.map(line(2, 3)) ]
      , 3
      , 3
      , 3
      )
  )

Answer 2

Functional programming is more about higher-order functions than direct recursion. I believe the following is equivalent to your example, using _.range from underscore.js and map and flatMap from the standard library.

const rowRange = _.range(3, rows + 1, 2);
const colRange = _.range(3, columns + 1, 2);
return rowRange.flatMap(row => colRange.map(col => [col, row]));

Answer 3

At first, on reading your code, I thought you generated one style of grid, so that makeGrid (7, 9) would result in something like this:

[
  [[3, 3], [3, 5], [3, 7], [3, 9]], 
  [[5, 3], [5, 5], [5, 7], [5, 9]], 
  [[7, 3], [7, 5], [7, 7], [7, 9]]
]

Instead, it returns a single array of pairs:

[[3, 3], [3, 5], [3, 7], [3, 9], [5, 3], [5, 5], [5, 7], [5, 9], [7, 3], [7, 5], [7, 7], [7, 9]]

I'm pretty sure I'm not the only one. Bergi suggested a fix in the comments to change it to the former. (That's what changing grid =[...grid, ...row] to grid =[...grid, row] would do.) And the wonderful answer from Thankyou is predicated on the same assumption.

This is a problem.

When the reader can't quickly understand what your code does, it becomes much harder to maintain... even for yourself just a few weeks later.

The reason you may hear advice to replace loops with recursion is related to this. Loops are all about explicit imperative instructions to get what you want, depending on mutating variables, which then you have to keep track of, and easily subject to off-by-one errors. Recursion is usually more declarative, a way of saying that the result you're looking for is just a matter of combining these simpler results with our current data, and pointing out how to get the simpler results, through either a base case or a recursive call.

The advantage in readability and understandability, though, is the key, not the fact that the solution is recursive.

Don't get me wrong, recursion is one of my favorite programming techniques. The answer from Thankyou is beatiful and elegant. But it's not the only technique which will fix the problems that explicit for-loops present. Usually one of the first things I do when trying to move junior programmer to intermediate and beyond is to replace for-loops with more meaningful constructs. Most loops are trying to do one of a few things. They're trying to convert every element of a list into something new (map), trying to choose some important subset of the elements (filter), trying to find the first important element (find), or trying to combine all the elements into a single value (reduce). By using these instead, the code become more explicit.

Also important, as seen in the answer from Thankyou, is splitting out reusable pieces of the code so that your main function can focus on the important parts. The version below extracts a function rangeBy, which adds a step parameter to my usual range function. range creates a range of integers so that, for instance, range (3, 12) yields [3, 4, 5, 6, 7, 8, 9, 10, 11, 12] rangeBy adds an initial step parameter, so that range (2) (3, 12) yields [3, 5, 7, 9, 11].

We use that rangeBy function along with a map, and its cousin, flatMap to make a more explicit version of your looped function:

const rangeBy = (step) => (lo, hi) => 
  [... Array (Math .ceil ((hi - lo + 1) / step))] 
    .map ((_, i) => i * step  + lo)

const createGrid = (rows, columns) => 
  rangeBy (2) (3, rows) .flatMap (y => 
    rangeBy (2) (3, columns) .map (x => 
      [y, x]
    )
  )

console .log (createGrid (7, 9))

Knowing what rangeBy does, we can mentally read this as

const createGrid = (rows, columns) => 
  [3, 5, 7, ..., rows] .flatMap (y => 
    [3, 5, 7, ..., columns] .map (x => 
      [y, x]
    )
  )

Note that if you want the behavior I was expecting, you can achieve it just by replacing flatMap with map in createGrid. Also, if you do so, it's trivial to add the more generic behavior that Thankyou offers, by replacing [y, x] with f (x, y) and passing f as a parameter. What remains hard-coded in this version is the conversion of rows and columns into arrays of odd numbers starting with 3. We could make the actual arrays the arguments to our function, and applying rangeBy outside. But at that point, we're probably looking at a different function ideally named cartesianProduct.

---

So recursion is an amazing and useful tool. But it's a tool, not a goal. Simple, readable code, however, is an important goal.

Update

I meant to mention this originally and simply forgot. The following version demonstrates that the currying in rangeBy is far from fundamental. We can use a single call easily:

const rangeBy = (step, lo, hi) => 
  [... Array (Math .ceil ((hi - lo + 1) / step))] 
    .map ((_, i) => i * step  + lo)

const createGrid = (rows, columns) => 
  rangeBy (2, 3, rows) .flatMap (y => 
    rangeBy (2, 3, columns) .map (x => 
      [y, x]
    )
  )

console .log (createGrid (7, 9))

The main rationale for currying rangeBy is that when it's written like this:

const rangeBy = (step) => (lo, hi) => 
  [... Array (Math .ceil ((hi - lo + 1) / step))] 
    .map ((_, i) => i * step  + lo)

we can write the more common range by simply applying 1 to the above. That is,

const range = rangeBy (1)

range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

This is so useful that it's become my usual style for writing functions. But it is not a significant part of the simplification of your problem.