尾递归与头经典递归
我经常听到Scala课程和解释:"但在实际代码中我们不使用递归,而是使用尾递归".
这是否意味着在我的Real代码中我不应该使用递归,但是尾递归非常类似于循环并且不需要史诗短语"为了理解递归,您首先需要理解递归".
实际上,考虑到你的堆栈..你更可能会使用类似循环的尾递归.
我错了吗？这种"经典"递归是否仅适用于教育目的,让您的大脑回到大学过去？
或者,尽管如此,我们还可以使用它..递归调用的深度小于X(其中X是堆栈溢出限制).或者我们可以从经典递归开始编码,然后,害怕你的堆栈吹了一天,应用几个重构使它像尾巴一样在重构领域使用更强大？
问题:你会使用/在你的真实代码中使用'经典头'递归的一些真实样本,可能还没有重构为尾部的一个？
尾递归==循环
您可以采用任何循环并将其表示为尾递归调用.
背景:在纯FP中,一切都必须产生一些价值.whilescala中的循环不会导致任何表达式,只会产生副作用(例如更新某些变量).它的存在只是为了支持来自命令背景的程序员.Scala鼓励开发人员重新考虑用while递归替换循环,这总是会产生一些价值.
所以根据Scala:递归是新的迭代.
但是,先前的陈述存在一个问题:虽然"常规"递归代码更容易阅读,但它带来性能损失并且存在堆栈溢出的固有风险.另一方面,尾递归代码永远不会导致堆栈溢出(至少在Scala*中),并且性能将与循环相同(事实上,我确信Scala将所有尾递归调用转换为普通的旧迭代).
回到问题,坚持"常规"递归没有错,除非:
- 您在计算大数时使用的算法(堆栈溢出)
- Tail Recursion带来了明显的性能提升