1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It is actually not the case that any recursive function can be re-written iteratively. Perhaps the most famous example is the Ackermann function. $\endgroup$ – Matt Werenski Jun 14 at 1:22
  • 1
    $\begingroup$ @Matt What do you define as "iteratively"? It's certainly possible to write the Ackermann function "iteratively" if you are allowed to use a stack! $\endgroup$ – Aaron Rotenberg Jun 14 at 2:54
1
$\begingroup$

It is impossible to do this in $O(n \log m)$ space, by a counting argument. Fix $n = 2$ and consider the number of iterations for which the program must execute. There are $m$ nested loops, each with $2$ indices, so the inner statement executes exactly $2^m$ times and then the iteration terminates. But the configuration space of the program only has $2^{O(\log m)} = \operatorname{poly}(m)$ possible states. So as $m \rightarrow \infty$, by the pigeonhole principle some state must be visited twice during the iteration, which is impossible because it would result in an infinite loop.

On the other hand, you can easily do this in $O(\log(n^m)) = O(m \log n)$ space. (Note that this is reversed from what you wrote!) All you have to do is count in base $n$. That is, keep an array of integers of size $\log n$ and treat them as the base $n$ digits of a single number that you are incrementing. Or you can use an arbitrary precision integer data type and use division and modulo operators to extract the base $n$ digits. Either way, this is trivially equivalent to using a stack, but maybe it feels less "recursive" to you.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yeah, I realized this a couple minutes before you answered, though I came at it from a different angle (I think--your answer was a bit more rigorous than I could follow): the index into the array at each depth is an independent variable, thus there is no way to calculate one based on the others. All independent variables must be tracked separately, requiring O(m lg(n)) space. Also, it's good to know not all recursive functions can be done iteratively! $\endgroup$ – dx_over_dt Jun 17 at 15:05
  • $\begingroup$ @dx_over_dt That is a reasonable intuitive explanation, and it might be possible to make it rigorous. It is worth taking the time to understand my counting argument proof too though, since similar arguments that apply the pigeonhole principle to the state space of a program can be used in many other situations. For example, this is the idea behind the pumping lemma for regular languages. $\endgroup$ – Aaron Rotenberg Jun 18 at 5:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.