Functional Programming - Lots of emphasis on recursion, why?

Posted by peakit on Stack Overflow See other posts from Stack Overflow or by peakit
Published on 2012-09-30T07:42:17Z Indexed on 2012/09/30 15:37 UTC
Read the original article Hit count: 420

Filed under:

scala

|

recursion

|

functional-programming

|

tail-recursion

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.

© Stack Overflow or respective owner

Related posts about scala

ensime scala errors (class scala.Array not found, object scala not found)

as seen on Stack Overflow - Search for 'Stack Overflow'
I've installed ensime according to the README.md file, however, I get errors in the inferior-ensime-server buffer with the following: INFO: Fatal Error: scala.tools.nsc.MissingRequirementError: object scala not found. scala.tools.nsc.MissingRequirementError: object scala not found. at scala… >>> More
infinite loop shutting down ensime

as seen on Stack Overflow - Search for 'Stack Overflow'
When I run M-X ensime-disconnect I get the following forever: string matching regex `\"((?:[^\"\\]|\\.)*)\"' expected but `^@' found and I see this exception when I use C-c C-c Uncaught exception in com.ensime.server.SocketHandler@769aba32 java.net.SocketException: Broken pipe at java… >>> More
How to resolve java.nio.charset.UnmappableCharacterException in Scala 2.8.0?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm using Scala 2.8.0 and trying to read pipe delimited file like in code snipped below: object Main { def main(args: Array[String]) :Unit = { if (args.length > 0) { val lines = scala.io.Source.fromPath("QUICK!LRU-2009-11-15.psv") for (line <-lines) print(line) } … >>> More
Question on Scala Closure (From "Programming in Scala")

as seen on Stack Overflow - Search for 'Stack Overflow'
I don't understand why authors said that Code Listing 9.1 from "Programming in Scala" use closure. In chapter 9, they show how to refactor code into more less duplicated form, from this original code: object FileMatcher { private def filesHere = (new java.io.File(".")).listFiles def filesEnding(query:… >>> More
Common idiom in Java to Scala, traverse/Iterate Java list into Scala list

as seen on Stack Overflow - Search for 'Stack Overflow'
I am processing a XML document and iterating through nodes. I want to iterate through the nodes and build a new List of some type. How would I do this with Scala: Here is my XML traverse code: def findClassRef(xmlNode: Elem) = { xmlNode\"classDef" foreach { (entry) => val name… >>> More

Related posts about recursion

tail recursion vs. forward recursion

as seen on Stack Overflow - Search for 'Stack Overflow'
Can someone give me the difference between these two kinds recursions and example? specifically in ocaml. Thanks >>> More
Are there advantages for using recursion over iteration - other than sometimes readability and elegance?

as seen on Programmers - Search for 'Programmers'
I am about to make two assumptions. Please correct me if they're wrong: There isn't a recursive algorithm without an iterative equivalent. Iteration is always cheaper performance-wise than recursion (at least in general purpose languages such as Java, C++, Python etc.). If it's true that recursion… >>> More
Python recursive function error: "maximum recursion depth exceeded"

as seen on Stack Overflow - Search for 'Stack Overflow'
I solved Problem 10 of Project Euler with the following code, which works through brute force: def isPrime(n): for x in range(2, int(n**0.5)+1): if n % x == 0: return False return True def primeList(n): primes = [] for i in range(2,n): if isPrime(i): … >>> More
Dynamic Programming Recursion and a sprinkle of Memoization

as seen on Stack Overflow - Search for 'Stack Overflow'
I have this massive array of ints from 0-4 in this triangle. I am trying to learn dynamic programming with Ruby and would like some assistance in calculating the number of paths in the triangle that meet three criterion: You must start at one of the zero points in the row with 70 elements. Your… >>> More
How does the recursion here work?

as seen on Stack Overflow - Search for 'Stack Overflow'
code 1: public static int fibonacci (int n){ if (n == 0 || n == 1) { return 1; } else { return fibonacci (n-1) + fibonacci (n-2); } } how can you use fibonacci if you haven't gotten done explaining what it is yet? I've been able to understand… >>> More