尾递归与迭代算法的区别

Question

我找不到文章描述为什么尾递归函数应该优先于迭代算法。

我不是在问尾递归为什么比简单递归更好，因为我认为这已经得到了清晰的解释。

那么为什么呢？

sum(n) = {
    def sumImpl(n, acc) = if(n <= 0) acc  else sumImpl(n - 1 , n + accumulator)
    sumImpl(n, 0)
}

更可取

sum = 0;
while(n--) sum += n

- raisercostin

---

对于它的自证正确性而言，事实上你的第二个片段确实是不正确的——它等价于 sum1(n-1)，其中我用 sum1 代替了你也称为 sum 的第一个函数。手动迭代往往比其语法递归形式更容易出现此类错误。具体来说，while(n--) 在将 n 加入累加器之前会使 n 减一，因此第一个 n 值被忽略了。 - Will Ness

Answer 1

递归使程序更易读，但性能较差。迭代过程具有良好的性能，但不那么易读，并且可能需要局部变量来存储中间值（可变性）。使用尾递归，您将获得两全其美的效果，而且不需要“sum”变量（不可变性）。这在计算大数和或阶乘时非常有用，因为您只需将结果转发到下一个递归函数调用即可避免堆栈溢出异常。

在并行环境中，不可变性非常重要。尝试编辑代码并将非常大的数字传递给函数以查看差异。

进一步阅读请点击 这里。

- sgud

---

在先前的情况下，函数式方法并不更易读。但我应该选择哪个版本呢？ - raisercostin

你的例子很简单。在这种情况下，迭代是显而易见的选择。要了解迭代、递归和尾递归调用之间的区别，请尝试这个链接：http://ideone.com/i0md7 - sgud

所以您的意思是尾递归的效率可能比迭代更高（斐波那契数列的效率可以高出6倍）？ 斐波那契数列 - 位置: 10000 时间: 137275432 纳秒 尾递归斐波那契数列 - 位置: 10000 时间: 20357861 纳秒 我会自己检查的:D。谢谢 - raisercostin

Answer 2

我认为答案在于你选择的编程范式。

声明式风格（如函数式编程中的Scala）与命令式风格（如Java中的迭代）。

在函数式范式中，我们希望避免副作用。因此，我们希望处理表达式，即返回值的代码。使用递归函数是一种方法。

在Java中，我们可能会在循环内更改对象的状态，这将被视为副作用。

总之，两种方法都不一定是坏的。然而，在函数式语言中，我们应该避免使用命令式结构，如循环，而应使用递归。

- Simon1729

Answer 3

递归消耗更多的内存（堆栈帧的开销）和更多的CPU周期（创建和销毁堆栈帧的开销）。但它使代码更易读。迭代使代码不太易读，但释放更多的内存和CPU，因此在受限环境下可能需要，例如物联网设备、手机等。请参阅此处的良好描述https://www.ocf.berkeley.edu/~shidi/cs61a/wiki/Iteration_vs._recursion#:~:text=Iteration%20and%20recursion%20are%20both%20ways%20to%20achieve%20repetition%20in%20programs.&text=All%20iterative%20functions%20can%20be,is%20defined%20as%20tail%20recursion。

- Ranjit Kumar

---

虽然递归消耗更多的内存，但尾递归不会，并且可以直接转换为迭代而不消耗堆栈帧。有时候迭代比尾递归更容易理解，问题是为什么仍然偏爱尾递归？这只是一种纯粹主义的方法吗？ - raisercostin