Recursion and tail recursion

Similar functions provide all sorts of alternatives to writing an explicit for loop, and F# does also have an explicit for statement.

However, the most celebrated way of avoiding iteration in functional programming is to use its more sophisticated alternative, recursion.

If you are already happy with the idea of recursive functions then you fill find F# and recursion easy. Of course the unlikely word is “happy” – most programmers, even experienced programmers, aren’t happy about recursion. It is often the case that where recursion occurs naturally, such as in the calculation of factorials or traversing trees it is easy to understand. However functional languages tend to use recursion for tasks that don't seem to be particularly naturally recursive. So let's take a look at how a general iteration can be converted to a recursion.

Let’s look at a very simple example – sum the first N integers recursively.

A recursive definition means that the function is defined in terms of itself and to make sure that this isn’t a mistake, i.e. to make it certain that you intended to use the function in its definition, you have to use the keyword “rec” for recursive.

The first thing to note is that SumN(0) has to be zero and if the parameter is any other value than zero then SumN(n)=n+SumN(n-1). With these two observations the recursion is easy to write:

let rec SumN n = 
 if n=0 then 0 else n + SumN(n-1)

The function can be used as normal, for example:

printfn "%A" (SumN 10)

Recursion also bothers many programmers because it seems to be very inefficient.

Consider what happens with SumN 10. First SumN 10 is called which starts to evaluate 10+SumN 9 but has to wait until SumN 9 has finished computing the sum of the first nine integers. Of course, SumN 9 has to wait while SumN 8 evaluates, which waits while SumN 7 evaluates and so on..

When we reach Sum 0 then a result is returned and the whole waiting stack of functions “unwinds” in the reverse order they were called in doing the sum and building up the final result. This is easy but inefficient because all of the suspended copies of the function’s expression have to be kept alive on the stack until it all unwinds. Not good.

The best form of recursion is called “tail recursion” simply because it doesn’t leave a waiting trail of part-completed expressions on the stack.

In tail recursion the recursive function ends with a simple call to itself and nothing more. What you have to do to create a tail recursive form of the function is to find a way to pass the computation down the recursion as it happens rather than do the job on the way “back up”.

Often this requires an additional parameter used to carry the result to the last recursive function call. For example, our sum of the first N integers can be re-written in tail recursive form as:

let rec SumN n acc =
 if n=0 then acc
   else SumN (n-1) (n+acc)

The new acc parameter accumulates the result as the recursion proceeds and when we finally get to n=0 the result is returned.

In this case there is no need to keep track of the recursion and the compiler optimises things so that only a single stack frame is used.

You can usually transform a recursion to tail recursion using this sort of result but it can be complicated and there is very little help in doing the job.

The compiler doesn’t even indicate when a function is tail recursive. Should you worry about this subtle point? You should at least know about tail recursion because functional programmers often talk about it, but in the main it’s an optimisation and can be left for a later version of your application.

Currying

In using the previous tail recursive sum you have to adopt a slightly unnatural calling convention because of the need to initialise acc.

For example to sum the first 10 integers you need to use:

printfn "%A" (SumN 10 0)

As the accumulator always has to be initialised to zero we can create a new function from SumN with the second parameter set to 0 – this is called “currying”:

let Sumn n=SumN n 0

Now we can call Sumn without having to specify the zero:

printfn "%A" (Sumn 10 )

The bigger picture

This article has concentrated on some of the key ideas in functional programming, in particular how to accept the almost paradoxical (to the procedural programmer) idea of immutability.

What we haven’t examined in detail are the benefits of this approach – implementing parallelism in particular. Also missed out are the many powerful, but perhaps not so functionally pure, facilities of the language.

F# isn’t an academic language and often the best way to express an idea is to use imperative or procedural programming and F# has the facilities you need – it has for loops, while loops and so on. It also has lots of interoperability with the .NET class library – and did I mention that it’s also object-oriented.

Most of these non-functional innovations are fairly familiar and you should be able to make progress with the help of the manual and a few examples.

<ASIN:047052801X>

<ASIN:0521513383>