While循环不能完成递归的例子

本文关键字：递归 循环 不能 While | 更新日期: 2023-09-27 18:02:50

在某些情况下，递归是必要的，或者甚至比javascript或c#中的while循环更可取(不管哪一种，用法似乎是相同的)。

MSDN上有一个阶乘示例(我删除了不相关的内容):

function factorial(num)
{
    var tmp = num;
    while (num-- > 2) {
        tmp *= num;
    }
    return tmp;
}

和

function factorial(num)
{
     return (num * factorial(num - 1));
}

简而言之，是否存在第二个示例优于第一个性能的情况。它能做到第一个例子不能做到的事情吗?如果有，那是什么?

While循环不能完成递归的例子

同样，递归算法(或实现)不是固有的比迭代的慢。事实上，每个递归算法都可以由等价的迭代实现实现，代价是必须自己跟踪一些中间/临时值，递归版本会自动跟踪函数调用堆栈。-递归代码比非递归代码慢吗

简而言之，有一种方法可以迭代地编写它，而不是递归方法。然后就出现了诸如java或python中的开销与C中存在的快捷方式相比的问题，在C中，您的开销递归最终会在方法中跳转。

在Javascript中，在ES2015之前，递归不是尾部结束的，所以从长远来看，递归会变得非常缺乏成本。从性能:Javascript中的递归与迭代，然而在此之后，Javascript确实有TER/TCO，因此投资递归的成本更低。在我看来，这是在JS中两者之间的个人偏好。如果你能使代码的递归功能和外观干净而快速，它的性能将大致与迭代版本相当，迭代版本可能变得非常难以跟踪甚至调试。

在c#中，递归通常比迭代解决方案慢，代价是可读性。然而，这再次归结为个人偏好。c#会在每个"循环/步骤"上创建开销和一个新的堆栈帧，因此它的性能通常不那么高。在其他语言中，递归与迭代解决方案一样强大。

对于许多语言，情况并非如此，递归也同样是或比迭代版本性能更好

参见:首选递归?关于为什么在Java、c#等开销不足的语言之外的语言中更受欢迎的一些额外的问题解答。

如果你可以用recursion解决的任务，你可以用loops解决，反之亦然。在递归中，方法的作用域一次又一次地创建相同的作用域。因此，如果您的方法的大小是1KB在10步骤递归，您的逻辑将花费10KB空间。在循环中，花费的空间将仅为1KB。

有些任务可以通过递归轻松解决，但使用循环就很难了。其中之一是河内塔

我完全同意前面的答案:递归通常方便集中。最好将问题简化为检查是否完成，如果没有完成，再加上一个简单的处理步骤。让操作系统来处理你的记账。

我要补充一点，有些函数不是原始的递归的;最著名的(也是最先发现的)是阿克曼函数。实际上，你可以用循环和你自己的堆栈来实现它，但是你真的，真的不想这么做。

在更实际的术语中，您不太可能需要实现一个不是原始递归的函数。Ackerman函数在理论上很有趣，但在日常生活中我们不会碰到它，即使在深度学习或高性能计算中也是如此。

你的问题的关键点是函数堆栈。return (num * factorial(num - 1));不在尾部位置，也就是说，递归调用factorial(num - 1)不是递归函数的最后一个动作。最后一个动作是与num相乘。所以你的factorial需要堆栈工作。当您使用尾部递归版本factorial(acc * num, num - 1)消除堆栈时，您需要使用额外的参数来模拟堆栈，即acc。

循环本身不如递归表达，因为缺少堆栈。这意味着您不能实现与非尾部递归实现等效的循环版本。实际上，您的while实现相当于factorial的尾部递归版本。尾部递归意味着所有递归调用共享一个堆栈帧，因此被消除——不再有堆栈。您的tmp只是acc—它模仿函数堆栈并累积迭代的结果。尝试用while循环实现factorial，但没有tmp这样的额外变量。

然而，非尾部递归解决方案的问题是它们可能会破坏堆栈，而tmp只是存储在堆上。

这是尾部递归的完整解:

function fact(acc, num) {
  return num > 1
   ? fact(acc * num, num - 1) // tail recursive case
   : acc; // base case
}
console.log(fact(1, 5));

结论:

在某些情况下，递归是否必要，甚至比while循环更可取

。尾递归和简单循环是等价的。除了非尾递归函数将其中间结果存储在函数堆栈中，因此可能发生堆栈溢出之外，非尾递归和具有自己堆栈的循环几乎是等效的。具有自己堆栈的循环将其存储在堆中，因此没有此限制。

相关文章：