node.js - 将树递归展开为迭代程序

Question

我编写了一个库，可以在给定规范对象( https://github.com/rgrannell1/revexp )的情况下生成任意字符串，并且我想将读取规范的函数从递归算法转换为迭代算法。由于我正在遍历的规范的深度，我遇到了 stackoverflow 错误。
我相信我需要从使用调用堆栈转向使用显式堆栈，但我以前从未这样做过。我已经阅读了以前关于 StackOverflow 的帖子，但我并没有完全理解如何将解决方案应用于这个问题。
这是一个示例规范对象。

const data = {
  every: [
    {
      digit: { zero: false }
    },
    {
      repeat: {
        value: { digit: {} }
      }
    }
  ]
}

以及算法当前如何遍历规范并生成与规范匹配的字符串的最小示例。

const fromSpec = (data) => {
  if (data.every) {
    return fromSpec.every(data)
  } else if (data.digit) {
    return fromSpec.digit()
  } else if (data.repeat) {
    return fromSpec.repeat(data.repeat)
  }
}

fromSpec.digit = () => {
  return Math.floor(Math.random() * 10)
}

fromSpec.every = part => {
  let message = ''

  for (const elem of part.every) {
    message += fromSpec(elem)
  }

  return message
}



fromSpec.repeat = part => {
  let message = ''
  
  // -- just using fixed repeat for the example
  for (let ith = 0; ith < 10; ++ith) {
    message += fromSpec(part.value)
  }

  return message
}

const result = fromSpec(data)
result // 1034856872

我很感激有关如何遍历此数据结构并以迭代而不是递归方式生成输出字符串的任何建议。

Answer 1

以下示例修改代码以使用堆栈数据结构。堆栈上的数据以增量方式处理，每次迭代都可能添加新数据。

const fromSpec = (data) => {
    const stack = [data];
    let message = '';
    while (stack.length > 0) {
        const item = stack.pop();
        // Assumption based on the code in the question:
        //   'every', 'digit', and 'repeat' keys are mutually exclusive.
        if (item.every) {
            // Add items in reverse order, so that items are popped off the stack
            // in the original order.
            for (let i = item.every.length - 1; i >= 0; --i) {
                stack.push(item.every[i]);
            }
        } else if (item.digit) {
            message += String(Math.floor(Math.random() * 10));
        } else if (item.repeat) {
            for (let i = 0; i < 10; ++i) {
                stack.push(item.repeat.value);
            }
        }
    }
    return message;
}

对于更复杂的场景(例如，当树中的 Node 需要处理 1)在遍历中最初遇到时和 2)在其所有子 Node 都被遍历之后，需要另一种方法。
以下链接可能是相关的。

https://web.archive.org/web/20120227170843/http://cs.saddleback.edu/rwatkins/CS2B/Lab%20Exercises/Stacks%20and%20Recursion%20Lab.pdf

https://web.archive.org/web/20161206082402/https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/recursionConversion/page/recursionConversion.html