scala - 函数式编程 - 非常强调递归，为什么？

Question

我正在了解函数式编程 [FP](使用 Scala)。从我最初的学习中得出的一件事是 FP 严重依赖递归。而且，在纯 FP 中，执行迭代操作的唯一方法似乎是编写递归函数。

由于递归的大量使用，FP 必须担心的下一件事情似乎是 StackoverflowExceptions，通常是由于长时间的递归调用而导致的。这是通过引入一些优化来解决的(从 Scala v2.8 开始，在堆栈帧维护和 @tailrec 注释中与尾递归相关的优化)

有人可以告诉我为什么递归对于函数式编程范例如此重要吗？如果我们迭代地做一些事情，函数式编程语言的规范中是否有一些东西会被“违反”？如果是，那么我也很想知道。

PS:请注意，我是函数式编程的新手，因此如果现有资源解释/回答了我的问题，请随时向我指出。另外，我确实了解 Scala 特别提供了对迭代操作的支持。

Answer 1

Church Turing thesis强调了不同可计算模型之间的等效性。

使用递归，我们在解决某些问题时不需要可变状态，这使得用更简单的术语指定语义成为可能。因此，从形式上讲，解决方案可以更简单。

我认为 Prolog 比函数式语言更好地展示了递归的有效性(它没有迭代)，以及我们在使用它时遇到的实际限制。