javascript - 为什么在 JS 中递归比迭代快？

问题描述

我一直在解决 LeetCode 上的 JS 问题，并注意到在几乎所有情况下，递归解决方案都比迭代解决方案运行得更快（例如，带有堆栈的 DFS 与递归）。

我在网上查找了几篇关于性能的博客文章，得出了类似的结论。 https://www.c-sharpcorner.com/blogs/performance-of-recursion-vs-loop-using-javascript

Oreily 的书，就像关于该主题的大多数正式材料一样，指出迭代性能更高，因为我理解的“开销更低”，但为什么在实践中不是这样呢？ https://www.oreilly.com/library/view/high-performance-javascript/9781449382308/ch04.html

我确实看到递归在特别大的堆栈大小时可能会失败，但它似乎总是比迭代更有效。这是怎么回事？我看到TCO还没有在JS中实现所以我很困惑。

标签： javascriptrecursion

好吧，要了解迭代中的递归（反之亦然），我们需要了解这两种技术的工作原理。

什么是递归？

它的功能自称。所以调用次数，函数属性的次数（包括变量，数据结构，主函数使用的子函数，将一遍又一遍地重新创建）。最后，编译器或（在 JavaScript 的情况下为 JIT）必须面临一些开销。
并且该过程将继续直到/除非找到基本情况，在这种情况下，递归期间的所有开销都将释放。
万一，如果没有找到/匹配基本情况，分配给这个特定函数的所有堆栈帧都将被耗尽，我们将得到类似的东西：Maximum call stack size exceeded

什么是迭代？

顾名思义，这是一个重复指令，将执行编码器给出的一些操作。
与递归相比，没有主堆栈框架将不会使用其他堆栈框架。并且函数的所有属性将一遍又一遍地用新值重新初始化。

根据我所做的比较，您可以清楚地得到一个想法，对于 Compiler 或 JIT，哪个更高，哪个效率更低。（并且它被推广到您将使用的每种语言）。

现在谈到性能，您提供的文章链接显然没有显示所有场景的准确测量。清楚地执行一个函数的时间主要取决于函数执行的指令数量。

查看以下片段，您可以重新考虑到目前为止的结论：

function nthFibo(a){
    if(a <= 2){
        return a;
    }else{
        return nthFibo(a-1)+nthFibo(a-2);
    }
   }


console.time("looping #1");  
console.log(nthFibo(45));
console.timeEnd("looping #1");

并检查迭代所需的时间，这将为您提供与递归相同的输出：

function nthFiboIterative(a){
    var first = 0, second = 1;
    var result = 0;
    var i = 1;
    while(i ++ <= a){
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}

console.time("looping #2");  
console.log(nthFiboIterative(45));
console.timeEnd("looping #2");

但这不是一个公平的测试，因为我们的第一个程序创建了一个指数过程，我们将其与第二个程序中的线性过程进行比较。让我们看看一个nthFibo演化出线性迭代过程的递归——

function nthFibo (a, x = 1, y = 1)
{ if (a == 0)
    return x;
  else
    return nthFibo(a - 1, y, x + y)
}

console.time("looping #3");  
console.log(nthFibo(45));
console.timeEnd("looping #3");

了解进程和过程（函数）之间的区别很重要。递归函数可以演化出递归过程、指数过程或迭代过程。类似地，非递归函数可以演变为迭代过程（想想简单的 for 循环）或指数过程（想想像 Ackerman 函数之类的东西）。

javascript - 为什么在 JS 中递归比迭代快？

问题描述

解决方案

推荐阅读