Functional Programming - Lots of emphasis on recursion, why?

Question

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 1

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.

Answer 2

Pure functional programming means programming without side effects. Which means, if you write a loop for instance, the body of your loop can't produce side effects. Thus, if you want your loop to do something, it has to reuse the result of the previous iteration and produce something for the next iteration. Thus, the body of your loop is a function, taking as parameter the result of previous execution and calling itself for the next iteration with its own result. This does not have a huge advantage over directly writing a recursive function for the loop.

A program which doesn't do something trivial will have to iterate over something at some point. For functional programming this means the program has to use recursive functions.

Answer 3

The feature that brings about the requirement that you do things recursively is immutable variables.

Consider a simple function for calculating the sum of a list (in pseudocode):

fun calculateSum(list):
    sum = 0
    for each element in list: # dubious
        sum = sum + element # impossible!
    return sum

Now, the element in each iteration of the list is different, but we can rewrite this to use a foreach function with a lambda argument to get rid of this problem:

fun calculateSum(list):
    sum = 0
    foreach(list, lambda element:
        sum = sum + element # impossible!
    )
    return sum

Still, the value of the sum variable has to be altered in each run of the lambda. This is illegal in a language with immutable variables, so you have to rewrite it in a way that doesn't mutate state:

fun calculateSum([H|T]):
    return H + calculateSum(T)

fun calculateSum([]):
    return 0

Now, this implementation will require pushing to and popping from the call stack a lot, and a program where all small operations would do this would not run very quickly. Therefore, we rewrite it to be tail recursive, so the compiler can do tail call optimization:

fun calculateSum([H|T], partialSum):
    return calculateSum(T, H + partialSum)

fun calculateSum([], partialSum):
    return partialSum

fun calculateSum(list):
    return calculateSum(list, 0)

Of course, if you want to loop indefinitely, you absolutely need a tail recursive call, or else it would stack overflow.

The @tailrec annotation in Scala is a tool to help you analyse which functions are tail recursive. You claim "This function is tail recursive" and then the compiler can tell you if you are mistaken. This is especially important in Scala as compared to other functional languages because the machine it runs on, the JVM, does not support tail call optimization well, so it is not possible to get tail call optimization in Scala in all the same circumstances you would get it in other functional languages.

Answer 4

TL;DR: recursion is used to handle inductively defined data, which are ubiquitous.

Recursion is natural, when you operate on higher levels of abstraction. Functional programming is not just about coding with functions; it is about operating on higher levels of abstraction, where you naturally use functions. Using functions, it is only natural to reuse the same function (to call it again), from whatever context where it makes sense.

The world is built by repetition of similar/same building blocks. If you cut a piece of fabric in two, you have two pieces of fabric. Mathematical induction is at the heart of maths. We, humans, count (as in, 1,2,3...). Any inductively defined thing (like, {numbers from 1} are {1, and numbers from 2}) is natural to handle/analyze by a recursive function, according to same cases by which that thing is defined/constructed.

Recursion is everywhere. Any iterative loop is a recursion in disguise anyway, because when you reenter that loop, you reenter that same loop again (just with maybe different loop variables). So it's not like inventing new concepts about computing, it's more like discovering the foundations, and making it explicit.

---

So, recursion is natural. We just write down some laws about our problem, some equations involving the function we're defining which preserve some invariant (under the assumption that the function is coherently defined), re-specifying the problem in simplified terms, and voila! We have the solution.

An example, a function to calculate the length of list (an inductively defined recursive data type). Assume it is defined, and returns the list's length, non-surprisingly. What are the laws it must obey? What invariant is preserved under what simplification of a problem?

The most immediate is taking the list apart to its head element, and the rest - a.k.a. the list's tail (according to how a list is defined/constructed). The law is,

length (x:xs) = 1 + length xs

D'uh! But what about the empty list? It must be that

length [] = 0

So how do we write such a function?... Wait... We've written it already! (In Haskell, if you were wondering, where function application is expressed by juxtaposition, parentheses are used just for grouping, and (x:xs) is a list with x its first element, and xs the rest of them).

All we need of a language to allow for such style of programming is that it has TCO (and perhaps, a bit luxuriously, TRMCO), so there's no stack blow-up, and we're set.

---

Another thing is purity - immutability of code variables and/or data structure (records' fields etc).

What that does, besides freeing our minds from having to track what is changing when, is it makes time explicitly apparent in our code, instead of hiding in our "changing" mutable variables/data. We can only "change" in the imperative code the value of a variable from now on - we can't very well change its value in the past, can we?

And so we end up with lists of recorded change history, with change explicitly apparent in the code: instead of x := x + 2 we write let x2 = x1 + 2. It makes reasoning about code so much easier.

---

To address immutability in the context of tail recursion with TCO, consider this tail recursive re-write of the above function length under accumulator argument paradigm:

length xs = length2 0 xs              -- the invariant: 
length2 a []     = a                  --     1st arg plus
length2 a (x:xs) = length2 (a+1) xs   --     the length of 2nd arg

Here TCO means call frame reuse, in addition to the direct jump, and so the call chain for length [1,2,3] can be seen as actually mutating the call stack frame's entries corresponding to the function's parameters:

length [1,2,3]
length2 0 [1,2,3]       -- a=0  (x:xs)=[1,2,3]
length2 1 [2,3]         -- a=1  (x:xs)=[2,3]
length2 2 [3]           -- a=2  (x:xs)=[3]
length2 3 []            -- a=3  (x:xs)=[]
3

In a pure language, without any value-mutating primitives, the only way to express change is to pass updated values as arguments to a function, to be processed further. If the further processing is the same as before, than naturally we have to invoke the same function for that, passing the updated values to it as arguments. And that's recursion.

---

And the following makes the whole history of calculating the length of an argument list explicit (and available for reuse, if need be):

length xs = last results
  where
     results = length3 0 xs
     length3 a []     = [a]
     length3 a (x:xs) = a : length3 (a+1) xs

In Haskell this is variably known as guarded recursion, or corecursion (at least I think it is).

Answer 5

There is nothing 'special' in recursion. It is widespread tool in programming and mathematics and nothing more. However, functional languages are usually minimalistic. They do introduce many fancy concepts like pattern matching, type system, list comprehension and so on, but it is nothing more then syntactic sugar for very general and very powerful, but simple and primitive tools. This tools are: function abstraction and function application. This is conscious choice, as simplicity of the language core makes reasoning about it much easier. It also makes writing compilers easier. The only way to describe a loop in terms of this tools is to use recursion, so imperative programmers may think, that functional programming is about recursion. It is not, it is simply required to imitate that fancy loops for poor ones that cannot drop this syntactic sugar over goto statement and so it is one of the first things they stuck into.

Another point where (may be indirect) recursion required is processing of recursively defined data structures. Most common example is list ADT. In FP it is usually defined like this data List a = Nil | Branch a (List a) . Since definition of the ADT here is recursive, the processing function for it should be recursive too. Again, recursion here is not anyway special: processing of such ADT in recursive manner looks naturally in both imperative and functional languages. Well, In case of list-like ADT imperative loops still can be adopted, but in case of different tree-like structures they can't.

So there is no anything special in recursion. It is simply another type of function application. However, because of limitations of modern computing systems (that comes from poorly made design decisions in C language, which is de-facto standard cross-platform assembler) function calls cannot be nested infinitely even if they are tail calls. Because of it, designers of functional programming languages have to either limit allowed tail-calls to tail recursion (scala) or use complicated techniques like trampoling (old ghc codegen) or compile directly to asm (modern ghc codegen).

TL;DR: There is no anything special in recursion in FP, no more than in IP at least, however, tail recursion is the only type of tail calls allowed in scala because of limitations of JVM.

Answer 6

Avoiding side effects is one of the pillars of functional programming (the other is using higher order functions).

Imagine how you might make use of imperative flow control without relying on mutation. Is it possible?

Of course for (var i = 0; i < 10; i++) ... depends on mutation (i++). In fact, any conditional loop construct does. In while (something) ... the something will depend on some mutable state. Sure, while (true) ... doesn't use mutation. But if you ever want out of that loop you'll need an if (something) break. Really, try to think of a (non-infinite) looping mechanism other than recursion that doesn't rely on mutation.

What about for (var x in someCollection) ...? Now we're getting closer to functional programming. The x can be thought of as a parameter to the body of the loop. Reusing the name isn't the same as reassigning a value. Perhaps in the body of the loop you're yield returning values as an expression in terms of x (no mutation).

Exactly equivalently, you could move the body of the for loop into the body of a function foo (x) ... and then map that over someCollection using a higher order function - replacing your loop construct with something like Map(foo, someCollection).

But then how is the library function Map implemented without mutation? Well, using recursion of course! It's done for you. It becomes less common to have to implement recursive functions yourself once you begin making use of the second pilar of higher order functions to replace your looping constructs.

Additionally, with tail call optimization a recursive definition is equivalent to an iterative process. You might also enjoy this blog post: http://blogs.msdn.com/b/ashleyf/archive/2010/02/06/recursion-is-the-new-iteration.aspx

Answer 7

There are two properties that I consider essential to functional programming:

1. Functions are first class members (only relevant, because to make it useful the second property is needed)

2. Functions are pure, i.e. a function called with the same arguments returns the same value.

Now if you program in an imperative style you have to use assignment.

Consider a for loop. It has an index and on each iteration the index has a different value. So you could define a function that returns this index. If you call that function twice you might get different results. Thus breaking the principle no 2.

If you break principle no 2. passing around functions (principle no 1) becomes something extremely dangerous, because now the result of the function might depend on when and how often a function gets called.

Answer 8

Last time I used a Functional language (Clojure) I was never even tempted to use recursion. Everything could be dealt with as a set of things, to which a function was applied to get part products, to which another function was applied, until the final result was reached.

Recursion is only one way, and not necessarily the clearest way, to handle the multiple items you usually have to handle to deal with any g

Answer 9

For the sake of new FP learners I would like to add my 2 cents.As mentioned in some of the answers, recursion is their to make use of immutable variables but why we need to do that ? its because it makes it easy to run the program on multiple cores in parallel, but why we want that ? Can't we run it in single core and be happy as always we have been ? No because content to process is increasing day by day and CPU Clock cycle can't be increased so significantly than adding more cores. From past one decade the clock speed has been around upto 2.7 ghz to 3.0 ghz for consumer computers and chip designers are having issues in fitting more and more transistors in their.Also FP has been their from very long time, but didn't pick up as it used recursion and memory was very expensive in those days but as clock speeds were soaring year after year so community decided to keep on going with OOP Edit: it was quite fast, I had only couple of minutes