scala - 尾递归 vs 头经典递归

Question

听我经常听到的Scala类(class)和讲解: “但在实际代码中，我们没有使用递归，而是使用尾递归” .

这是否意味着在我的 Real 代码中我不应该使用递归，而是使用尾递归非常像循环并且不需要史诗般的短语 “要了解递归，您首先需要了解递归” .

实际上，考虑到您的堆栈……您更有可能使用类似循环的尾递归。

我错了吗？ “经典”递归是否仅适用于教育目的，让您的大脑回到大学时代？

或者，对于所有这些，我们可以在某个地方使用它……递归调用的深度小于 X(其中 X 是您的堆栈溢出限制)。或者我们可以从经典递归开始编码，然后担心有一天你的堆栈会爆炸，应用几次重构使其像尾部一样，以便在重构领域更强大？

问题:您将使用/在您的 中使用了“经典头”递归的一些真实示例真实尚未重构为尾一的代码，也许？

Answer 1

尾递归 == 循环

您可以采用任何循环并将其表示为尾递归调用。

背景:在纯 FP 中，一切都必须产生某种值(value)。 while scala 中的循环不会产生任何表达式，只会产生副作用(例如更新某些变量)。它的存在只是为了支持来自命令式背景的程序员。 Scala 鼓励开发人员重新考虑更换 while递归循环，总是会产生一些值。

所以根据Scala:递归是新的迭代 .

但是，前面的语句存在一个问题:虽然“常规”递归代码更易于阅读，但它会带来性能损失，并且存在堆栈溢出的固有风险。另一方面，尾递归代码永远不会导致堆栈溢出(至少在 Scala* 中)，并且性能将与循环相同(事实上，我确信 Scala 将所有尾递归调用转换为普通的旧迭代)。

回到这个问题，坚持“常规”递归没有错，除非:

您在计算大数时使用的算法(堆栈溢出)

尾递归带来显着的性能提升