Functional Programming - Lots of emphasis on recursion, why?

scala recursion functional-programming tail-recursion
peakit picture peakit · Sep 30, 2012 · Viewed 10.5k times · Source

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.

Answer

CapelliC picture CapelliC · Sep 30, 2012

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.

Related questions

Reverse list Scala

Given the following code: import scala.util.Random object Reverser { // Fails for big list def reverseList[A](list : List[A]) : List[A] = { list match { case Nil => list case (x :: xs) => reverseList(xs) ::: List(x) } } // Works def reverseList2[A](…

Read More
Scala - convert List of Lists into a single List: List[List[A]] to List[A]

What's the best way to convert a List of Lists in scala (2.9)? I have a list: List[List[A]] which I want to convert into List[A] How can that be achieved recursively? Or is there any other better way?

Read More
How to call a method n times in Scala?

I have a case where I want to call a method n times, where n is an Int. Is there a good way to do this in a "functional" way in Scala? case class Event(name: String, quantity: Int, value: …

Read More