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.

Solution 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.

Solution 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.

Solution 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.

Solution 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).

Solution 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.

View more solutions

Comments

[peakit]

silly question - what would be the usefulness of a program which does not produce "side-effects" in a pure functional paradigm :-)

[Valentin Perrelle]

In pure functional programming, the result of the program is whatever is returned by the "root" function called. The theory defines the behaviour of program by the relation it creates between inputs and outputs. A Turing machine have a strip of a tape as input, changes it, and the results is what lies at the end of the execution. In functional programming, the input is the parameter of the function and the output is what it returns. We often use monads to handle various types of input/output in functionnal languages.

[Jens Schauder]

@peakit you are right the usefulness would be close to zero. So all real languages provide some means of causing side effects. But in languages like haskell they are confined to very special objects (IO-Monads)

[Lie Ryan]

@peakit: it is possible to have a pure functional language with no side effect, the most popular pure functional language is Haskell. In pure functional language, functions that do "side effect" (e.g. input/output) are thought of as a function that takes a "universe" as an argument and returns another "universe" (e.g. printLn takes a universe and returns a new universe with the console showing the printed string). Therefore, the language remains totally free of side effect, while still being useful in practice.

[Lie Ryan]

In pure functional languages, monads are nothing special. It's just a syntax sugar for passing the result of an expression to the next statement. A chain of "statements", a; b; c; can be thought of as c(b(a(U))), where U is the universe before the statement and each "statement" returns a new universe with the "side effect" of that statement applied.

[tangentstorm]

It's definitely possible to use imperative flow control without explicit loops, and various programming languages do so: APL, J, Sisal, Vector Pascal, to name a few. (If that doesn't count because the loop is still going on behind the scenes, then all functional languages are disqualified by the same logic.) Another approach is a data flow system where each processor has its own stateless, endless loop, and you chain them together to form an assembly line... Then you make the line itself go in a circle. :)

[AshleyF]

The point was that expressing iterative processes without using mutation requires expressing them recursively. Expressing without explicit loops is easy (e.g. the Map example mentioned).

[tangentstorm]

Yes but recursion itself relies on mutable state: the thing that's mutating is the call stack in the interpreter. It's just hidden from the developer. The array programming languages also hide the mutation, but it's not recursion under the hood. In J, you can say 'i. 5' and get '0 1 2 3 4', or '1 + i. 5' and you get '1 2 3 4 5'. Any mutable state involved is at the interpreter level, just like with lambda calculus style languages... But under the hood, it could be doing a loop or it could be doing all the addition steps in parallel (with intel's mmx / sse instructions, or your graphics card)

[AshleyF]

Ah, yes. I think I see your point about when I say, Map is implemented "...with recursion of course!". Not necessarily true. Not knowing J, I relate your example to F#: You can say [0..4] and get [0; 1; 2; 3; 4] or say List.map ((+) 1) [0..4] and get [1; 2; 3; 4; 5]. Under the hood List.map may use mutation as it sees fit. Indeed, it's all loads/stores at some point. The nice thing is to leave that kink of approach up to the compiler and library authors. We got away from goto years ago (though it's all branches at some point). Now let's get away from load and store.

[kqr]

Technically, Haskell doesn't have iteration either – just very clever abstractions around recursion that make it seem like it does when you need it. forM_ is like a normal foreach loop, but it is implemented in terms of mapping over a list of IO actions, and IO actions in turn can emulate mutability but are implemented with chained function calls.

[kqr]

With lazy evaluation, you don't even need a universe argument. You can think of the IO monad as building a tree of IO actions. That tree is returned to the runtime system by the main function, and then the runtime system parses the tree and performs the correct actions as they are encountered.

[davidhq]

Immutable state doesn't mean we cannot re-bind a variable (sum in this case), just that the data structure the variable points to can never be altered. But you are right that Erlang for example doesn't allow re-binding of variables.

[Will Ness]

@davidhq immutable variables and immutable data structures are two different things though.

[Jacco]

In other words: in the 'old days' functional programming came to a halt, because of hardware limitations. Nowadays, functional programming is the answer to... hardware limitations. Got to love the irony of that.