javascript - 尾调用优化递归函数

Question

这是一个深度扁平化数组的函数

const deepFlatten = (input) => {
  let result = [];
  input.forEach((val, index) => {
    if (Array.isArray(val)) {
      result.push(...deepFlatten(val));
    } else {
      result.push(val);
    }
  });
  return result;
};

在一次讨论中，有人告诉我它的内存效率不高，因为它可能会导致堆栈溢出。

我在 http://2ality.com/2015/06/tail-call-optimization.html 中读到我可能会重写它，以便它是 TCO-ed。

那会是什么样子，我如何衡量它的内存使用情况？

Answer 1

当您的递归调用在 forEach 内部时，您无法对其进行优化，因为为了应用 TCO，编译器需要检查您是否没有保存前一个调用的“状态”。在 forEach 的情况下，您确实保存了当前位置的“状态”。

为了使用 TCO 实现它，您可以重写要通过递归调用实现的 foreach，它看起来像这样:

function deepFlattenTCO(input) {
  const helper = (first, rest, result) => {
    if (!Array.isArray(first)) {
      result.push(first);
      if (rest.length > 0) {
        return helper(rest, [], result);
      } else {
        return result;
      }
    } else {
      const [newFirst, ...newRest] = first.concat(rest);

      return helper(newFirst, newRest, result);
    }
  };

  return helper(input, [], []);
}

console.log(deepFlattenTCO([
  [1], 2, [3], 4, [5, 6, [7]]
]));

您可以看到，在每个 return 中，唯一执行的操作是递归调用，因此，您不会在递归调用之间保存“状态”，因此编译器将应用优化。