recursion - 尾递归与迭代算法

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

Answer 1

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

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

在这里进一步阅读

Answer 2

递归消耗更多的内存（堆栈帧的开销）和更多的 CPU 周期（创建和销毁堆栈帧的开销）。然而，它使代码更具可读性。迭代降低了代码的可读性，但释放了更多的内存和 CPU，因此受限环境可能需要它，例如 IOT 设备、电话等。有关详细说明，请参见此处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。