Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.

Sydde

macrumors 68030
Original poster
Aug 17, 2009
2,575
7,069
IOKWARDI
I was casually reading through a long tutorial on one of those odd functional languages (Haskell) and got to wondering about the recursion thing. Obviously, recursive loops in a procedural language look kind of elegant but could present something of a risk if compiled verbatim (an arbitrarily long run might result in a stack overrun, especially on a secondary thread). In functional languages, it seems like recursive loops (in source) are the de facto technique, presumably the compiler either converts them to iterative or uses some other implementation to prevent stack issues.

My question is why do the functional languages (that I know of) prefer to express loops recursively? Is there some way that that construction looks more sensible to humans? Or is it simply that it is more concise?
 
I was casually reading through a long tutorial on one of those odd functional languages (Haskell) and got to wondering about the recursion thing. Obviously, recursive loops in a procedural language look kind of elegant but could present something of a risk if compiled verbatim (an arbitrarily long run might result in a stack overrun, especially on a secondary thread). In functional languages, it seems like recursive loops (in source) are the de facto technique, presumably the compiler either converts them to iterative or uses some other implementation to prevent stack issues.

My question is why do the functional languages (that I know of) prefer to express loops recursively? Is there some way that that construction looks more sensible to humans? Or is it simply that it is more concise?

Recursion is fundamental to the underlying mathematical model of functional programming. Iteration requires mutable state (some form of index counter), and cannot be expressed purely in terms of functions. Stack overflow is avoided by tail-call optimization.

At the most extreme, Church Numerals express even basic arithmetic and numeric values in terms of functions.
 
In iterative languages that don't normally support tail call optimization to limit stack growth a technique called trampolining can be used to minimize stack depth. Generally functional languages support tail call optimization, so stack frames are reused for each call.

-Lee
 
Functional programming emphasize functions over storing explicit state. Using a loop requires state explicit state in the form of an iterator.

I was casually reading through a long tutorial on one of those odd functional languages (Haskell) and got to wondering about the recursion thing. Obviously, recursive loops in a procedural language look kind of elegant but could present something of a risk if compiled verbatim (an arbitrarily long run might result in a stack overrun, especially on a secondary thread). In functional languages, it seems like recursive loops (in source) are the de facto technique, presumably the compiler either converts them to iterative or uses some other implementation to prevent stack issues.

My question is why do the functional languages (that I know of) prefer to express loops recursively? Is there some way that that construction looks more sensible to humans? Or is it simply that it is more concise?
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.