The Stack

In most languages, when a function is called, the function arguments and the return address of the calling function (possibly including other things like the frame pointer – which can be turned off in the likes of VC++) are pushed onto the stack. When the function call ends, these are popped from the stack and the function returns to the calling method.

The stack is finite, and per thread is by default 1MB in size (see Thread Stack Size). So obviously it’s possible to get to point where we get a StackOverflow exception. This is especially a problem with recursive functions.

Another issue with having deep stacks in .NET is when the garbage collector kicks in as it will have to traverse the entire stack each time garbage collection is required.

Tail Recursion/Tail Call

C# has no built in tail call mechanism, unlike F#. A tail call allows the .NET CLR to drop the current stack frame before executing the target function.

Let’s look at a really simple recursive function, which simply increments a value and outputs the result.

let rec increment i =
    if i < 100000 then 
        printfn "%d" i
        increment (i + 1)
        printfn "next"

The above will be terminated by a StackOverflowException very quickly. But if we remove the last printfn line to give

let rec increment i =
    if i < 100000 then 
        printfn "%d" i
        increment (i + 1)

we will find the function continues until completion.

So basically a tail call is where the recursive call is the last (or tail) function call. This doesn’t strictly mean the recursive call is the last line of the function, it’s that it’s the last called within the function. For example

let rec increment i =
    if i < 100000 then 
        printfn "%d" i
        increment (i + 1)
    else
        printfn "next"

shows that the recursive call is the last function call and only when the recursive calls are completed (and stack unwound) does the last line get executed. But beware, the recursive call should be the last call executed but if we alter the code slightly, to have it return an int we might have something like the following code

let rec increment i =
    if i < 100000 then 
        printfn "%d" i
        i + increment (i + 1)
    else
        printfn "%d" i
        0

This is contrived example, to force an int return (so don’t worry about what it actually does). Now the line i + increment (i + 1) is the last executed as the code goes recursive and it appears that increment (i + 1) is still the last line executed, however the inclusion of the i + code has mean’t this code is no longer tail recursive.

Further Reading

Tail call
Tail calls in F#