尾调用优化递归函数 [英] Tail Call Optimizing recursive function

问题描述

这是一个深度展平数组的函数

This is a function which deep-flattens an array

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

在讨论过程中，我被告知它不具有内存效率，因为它可能会导致堆栈溢出。

During a discussion, I was told it is not memory efficient, as it might cause stack overflows.

我在中读到http://2ality.com/2015/06/tail-call-optimization.html 我可能会重新编写它以便进行TCO编辑。

I read in http://2ality.com/2015/06/tail-call-optimization.html that I could potentially re-write it so that it is TCO-ed.

它看起来怎么样？如何衡量它的内存使用情况？

How would that look like and how could I measure it's memory usage profile?

推荐答案

你无法优化它当你的递归调用在 forEach 中时，因为为了应用TCO，编译器需要检查你是否保存了前一次调用的状态。如果 forEach ，您确实保存当前位置的状态。

You can't optimize it when your recursive call is inside forEach, because in order to apply TCO, the compiler need to check that you not saving a "state" of the previous call. In case of forEach you do save a "state" of the current position.

为了实现它TCO你可以用递归调用重写 foreach ，它看起来像这样：

In order to implement it with TCO you can rewrite that foreach to be implemented with the recursive call, it would look something like that:

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]]
]));

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

You can see that in each return the only operation that is executed is the recursive call, so, you don't save "state" between recursive calls, therefore the compiler will apply the optimization.

这篇关于尾调用优化递归函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！