Menu
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.
981
Tail Recursion Elimination is a very interesting feature available in Functional Programming languages, like Haskell and Scala. It makes recursive function calls almost as fast as looping.
Technically no, but practically yes. Recursion is far more common when you're taking a functional approach to the problem. As such, languages designed to use a functional approach often include features that make recursion easier/better/less problematic.
Recursion is central to a variety of the fastest sorting algorithms. Sorting algorithms aim to take in a list of numbers and return them from least to greatest. Since so many applications rely on quick sorts, finding an algorithm that can sort a list the fastest is of great interest.
What makes recursion confusing? The key reason is that we are looking at the same function with different values of local variables. It is very important to make sure which input is currently being used when you are analyzing a recursive function.
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.
113
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
