函数式编程 - 很多强调递归，为什么? [英] Functional Programming - Lots of emphasis on recursion, why?

问题描述

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

I am getting introduced to Functional Programming [FP] (using Scala). One thing that is coming out from my initial learnings is that FPs rely heavily on recursion. And also it seems like, in pure FPs the only way to do iterative stuff is by writing recursive functions.

而且由于递归的大量使用，FP 不得不担心的下一件事情是 StackoverflowExceptions 通常是由于冗长的递归调用.这是通过引入一些优化来解决的(从 Scala v2.8 开始，堆栈帧维护中的尾递归相关优化和 @tailrec 注释)

And because of the heavy usage of recursion seems the next thing that FPs had to worry about were StackoverflowExceptions typically due to long winding recursive calls. This was tackled by introducing some optimizations (tail recursion related optimizations in maintenance of stackframes and @tailrec annotation from Scala v2.8 onwards)

有人能告诉我为什么递归对函数式编程范式如此重要吗?如果我们迭代地做东西，函数式编程语言的规范中是否有一些东西会违反"?如果是，那么我也很想知道这一点.

Can someone please enlighten me why recursion is so important to functional programming paradigm? Is there something in the specifications of functional programming languages which gets "violated" if we do stuff iteratively? If yes, then I am keen to know that as well.

PS:请注意，我是函数式编程的新手，所以如果他们解释/回答我的问题，请随时向我指出现有资源.此外，我确实理解 Scala 也特别支持执行迭代操作.

PS: Note that I am newbie to functional programming so feel free to point me to existing resources if they explain/answer my question. Also I do understand that Scala in particular provides support for doing iterative stuff as well.

推荐答案

Church Turing论文强调了不同可计算性模型之间的等价性.

Church Turing thesis highlights the equivalence between different computability models.

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

Using recursion we don't need a mutable state while solving some problem, and this make possible to specify a semantic in simpler terms. Thus solutions can be simpler, in a formal sense.

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

I think that Prolog shows better than functional languages the effectiveness of recursion (it doesn't have iteration), and the practical limits we encounter when using it.

这篇关于函数式编程 - 很多强调递归，为什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！