函数式编程 - 对递归的重视程度很高，为什么？ [英] Functional Programming - Lots of emphasis on recursion, why?

问题描述

我将介绍函数式编程[FP]（使用Scala）。从我最初的学习中得出的一点是，FPs很大程度上依赖于递归。同样，在纯 FP中，做迭代的唯一方法是编写递归函数。

由于使用率很高的递归似乎是FPs不得不担心的下一件事情，通常是由于长时间递归调用而引起的 StackoverflowExceptions 。通过引入一些优化来解决这个问题（在维护堆栈框中进行与尾部递归相关的优化，并且从Scala v2.8开始注释 @tailrec ）

有人能告诉我为什么递归对函数式编程范例如此重要吗？函数式编程语言的规范中是否存在某些东西，如果我们迭代地执行某些东西，它会被违反？如果是的话，那么我也很想知道这一点。

PS：请注意，我是功能性编程的新手，所以如果他们解释我可以随意指向现有资源/回答我的问题。另外我也明白，Scala特别提供了对迭代内容的支持。 Church Turing论文强调了不同可计算性模型之间的等价性。

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

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

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.

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: 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 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.

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屋！