F#: A Tail of recursion

Get it? Tail recursion? It is a joke you see, you are not laughing, well, I am not being paid to make you laugh.

Anyway, in all seriousness if you are like me, you look around at various things, reading snippets about various languages and the concept of tail recursion keeps on coming up and it is rare that anyone really describes what on earth it is.

Recursion is a part of functional programming, you go through uni and more often than not the lectures will claim it is what makes a language functional, (they are wrong, but my anger towards the educaction of my profession is another story).

So what happens in normal recursion is that when your program calls a function it pushes the instruction pointer (the address in the program code that identifies the next operation to execute). Once the function returns the stack is cleared and the instruction pointer is restored and the program continues along its merry way. Simple stuff right, all coming back to you from your computer theory classes?

Anyway recursion can throw a spanner into the works, a stack generally has a fixed block of memory it is allowed to use, generally around 1mb, so if your recursive function is given a large amount of data to work through, you will most probably enter the realms of the stack overflow.

So this is where tail recursion comes into play, the idea behind tail recursion is that nothing will execute after the recursive call, since there is nothing left to execute after the recursive call there is no need to store the instruction pointer on the stack, so indeed the stack stays nice and safe and you will not see that dreaded stack overflow.

BUT I hear you say, that is all well and good for simple recursive functions, but what happens when I need to do some operations of the result?

To answer this, lets us do an example.

let rec fib = function

| 0 -> 0

| 1 -> 1

| n -> fib(n - 1) + fib(n - 2)

This is not a tail recursive function and infact if you wanted to know the fibonanci number of somethign stupidly large you will get a stack overflow.

What we know about fibonnaci numbers is x = (x -1) + (x -2) and when we are working out x we already know x -1 and x -2 so we can pass them around as parameters

let fib n =

let rec loop acc1 acc2 = function

| 0 -> acc1

| n -> loop acc2 (acc1 + acc2) (n -1)

loop 0 1 n