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.