递归函数本质上是资源密集型的

Are recursive functions resource-intensive by nature?

本文关键字：密集型 资源 本质上 递归函数      更新时间：2023-09-26

我查看了w3schools的web worker页面，注意到了以下代码：

var i=0;
function timedCount()
{
i=i+1;
postMessage(i);
setTimeout("timedCount()",500);
}
timedCount();

两个问题：

  1. 这被认为是递归函数吗
  2. 如果是，是资源密集型吗

我还不完全清楚递归函数的性质，但我记得听说每个递归调用都存储在内存中的某个地方。所有递归函数都是这样吗？如果这个函数运行足够长的时间，它最终会阻塞内存吗？

谢谢！

这不是递归，因为timedCount在调用下一个实例之前退出。如果你想这么说的话，这只是一个自我延续的延迟循环。（顺便说一句，使用setInterval而不是重复使用setTimeout会处理得更好。这个例子是一些非常糟糕的代码，就像大多数W3Fools资源一样。）

timedCount() -> setTimeout() -> end
    ^                |
    |                |
    +----------------+

这个是一个递归函数：

function recurse() {
    recurse();
}

这里建立了一个调用堆栈，外部recurse不会退出并离开堆栈，直到内部recurse调用返回，而内部recurse调用无限返回等等。由于这里任何地方都没有return，这最终会破坏堆栈；所以这就是你的资源使用。

recurse() -> recurse() -> recurse() -> recurse() -> recurse() -> ...

一般来说，递归是可以优化的，但您可以放心地假设javascript实现不会对递归进行优化。

关于您的两个具体问题：

  1. 这并不是一个严格意义上的递归函数。递归函数在函数体的某个地方调用自己。函数timedCount始终返回控制，从不直接或间接调用自己。在这种情况下，它将控制权返回到页面的事件循环，以便稍后由计时器再次调用
  2. 这意味着它确实试图确保自己会被再次调用，但因为它不是直接调用自己，所以不会填充堆栈空间。因此，随着时间的推移，它不会阻塞内存

对于timedCount来说，重要的是在返回之前不能再次调用它。无视平行性。

每个函数都在内存中的某个位置。

真的递归函数每次调用都会占用堆栈空间（就像其他函数一样），重要的是它递归了多少次。

我不认为这个例子是"递归的"，因为对timedCount的原始调用在定时器到期后再次调用之前结束。如果它看起来像这样：

function timedCount() {
  i = i + 1;
  postMessage(i);
  timedCount();
}

这将是递归的，并且会很快破坏堆栈，因为没有terminatal条件。

相关文章：