# Arbitrary depth nested for-loops without recursion

Suppose I have an array of `n` values I want to apply nested for-loops over to an arbitrary depth `m`.

``const array = [1, 2, 3];  // 2-depth for-loop for (const i of array) {   for (const j of array) {     // do the thing   } }  // 3-depth for-loop for (const i of array) {   for (const j of array) {     for (const k of array) {       // do the thing     }   } } ``

The obvious solution is to use recursion. In JavaScript/TypeScript, a generator lends itself well here. For an example problem, let’s calculate the probability distribution of the sum of rolling `m` 6-sided dice.

``type Reducer<T, TResult> = (current: T, accumulator?: TResult) => TResult;  function* nestForLoopRecursive<T, TResult>(   array: T[],   depth: number,   reduce: Reducer<T, TResult> ): Generator<TResult> {   for (const value of array) {     if (depth === 1) {       yield reduce(value);     } else {       for (const next of nestForLoopRecursive(array, depth - 1, reduce)) {         yield reduce(value, next);       }     }   } }  function reduceSum(current: number, prev = 0): number {   return current + prev; }  const pips = [1, 2, 3, 4, 5, 6];  interface RollDistribution {   [key: number]: number; }  function rollMDice(m: number): RollDistribution {   const results: RollDistribution = {};    for (const result of nestForLoopRecursive(pips, m, reduceSum)) {     results[result] = results[result] !== undefined ? results[result] + 1 : 1;   }    return results; }  for (let m = 1; m <= 3; m++) {   console.log(`Rolling \$  {m} \$  {m === 1 ? 'die' : 'dice'}`);   console.log(rollMDice(m));   console.log(); } ``

### Output

``Rolling 1 die { '1': 1, '2': 1, '3': 1, '4': 1, '5': 1, '6': 1 }  Rolling 2 dice {   '2': 1,   '3': 2,   '4': 3,   '5': 4,   '6': 5,   '7': 6,   '8': 5,   '9': 4,   '10': 3,   '11': 2,   '12': 1 }  Rolling 3 dice {   '3': 1,   '4': 3,   '5': 6,   '6': 10,   '7': 15,   '8': 21,   '9': 25,   '10': 27,   '11': 27,   '12': 25,   '13': 21,   '14': 15,   '15': 10,   '16': 6,   '17': 3,   '18': 1 } ``

My understanding is that any recursive function can be rewritten iteratively, though it usually requires some augmentation. (For example, an in-order traversal of a binary tree can be done iteratively if you augment each node with two bits and a parent pointer.)

How can I rewrite `nestForLoopRecursive()` without using a stack or any other recursive data structure? In particular, is it possible to do this in at most `O(n lg(m))` space?

Here’s a CodeSandbox with everything needed written in TypeScript. The code yet to be written starts at line 16. Feel free to answer using whatever language you choose, though, including pseudocode.