尾递归与迭代算法

Question

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

我不是问为什么尾递归比简单递归更好，我认为这在任何地方都得到了明确的解释。

所以为什么

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

优于

sum = 0;
while(n>0){ sum += n; n--;}

---

旧的有缺陷的版本（假设这不是因为这样的错误更容易发现）

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

Answer 1

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

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

进一步阅读这里

Answer 2

递归消耗更多的内存（堆栈帧的开销）和更多的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%20define%20as%20tail%20recursion.

Answer 3

我认为答案在于你选择的编程范式。 声明式风格（在函数式编程中使用，比如 Scala）与 命令式风格（想想java中的迭代）。

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

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

底线是，这两种方法都不一定是坏事。但是，我们应该避免使用命令式结构，例如函数式语言中的循环，而是使用递归。