Introduction

What is the easies way to cause the StackOverflowException? If you are familiar with recursion the answer is pretty straightforward – recursion. According to the documentation “Starting with the .NET Framework 2.0, you can’t catch a StackOverflowException object with a try/catch block, and the corresponding process is terminated by default”.

Neither me nor you want to come across such a problem. Some languages offers “tail call optimization” – optimization that can help to avoid the StackOverflowException.

The main question is what the tail call optimization is and why it is so powerful?

Let’s find out!

Tail call

First of all, let’s clarify what the “tail call” is. Wikipedia seems to be right place to start the research. We can find there that “a tail call is a subroutine call performed as the final action of a procedure.”.

Let’s consider following F# code snippets:

module StandardRecursion =
    let rec factorial x =
        if x < 1 then 1
        else x * factorial (x-1)

module TailRecursion =    
    let factorial x = 
       let rec factorial2 x acc =
            if x = 0 then acc
            else factorial2 (x-1) (acc * x)
       factorial2 x 1

There are two implementations of the factorial – first one uses standard recursion whereas second one uses tail recursion. Both functions do the same – compute the factorial of given argument.

Now let’s assume that for some unknown reason we want to run the following invocations:

    StandardRecursion.factorial 6000000
    TailRecursion.factorial 6000000

What will happen?

And there we go, the EXCEPTION. So, the whole application terminated and we are all happy (just kidding – we prefer when it’s running…).

Now let’s run the latter invocation and see what will happen… Ok, I didn’t put a screenshot here because the application didn’t crash! Surprised?

There is an explanation why the latter implementation of the factorial didn’t crash – tail call optimization.

Tail call optimization

The optimization is mentioned on the tail call Wikipedia page. At the very bottom of the page you can find that not all languages support it, hence don’t be surprised if your tail recursion crashes an application.

Regarding F# and the tail call optimization there is a simple and clear explanation of the optimization process :

“A tail recursive function is a special case of recursion in which the last instruction executed in the method is the recursive call. F# and many other functional languages can optimize tail recursive functions; since no extra work is performed after the recursive call, there is no need for the function to remember where it came from, and hence no reason to allocate additional memory on the stack.

F# optimizes tail-recursive functions by telling the CLR to drop the current stack frame before executing the target function. As a result, tail-recursive functions can recurse indefinitely without consuming stack space.”

To get better insights let’s look at the F# -> C# decomplication on sharplab.io:

As you can see the tail recursion implementation has been decompiled into a “while” loop whereas the standard recursion looks the same. Such a “while” loop is nowhere near as disastrous as the recursion in terms of StackOverflowException.

Summary

To sum up, tail call optimization is a powerful technique that compilers use to reduce the stack usage . However, not all languages support the optimization so it is worth to read the documentation first rather than kill the application by accident.

As always I’ve prepared an example and you can find it on my github, project: tail-call-csharp and tail-call-fsharp. The example consists of F# code and C# code. I haven’t mentioned the C# in this post but it turns out it doesn’t offer as much as F# in terms of tail call optimization. I figured out that for target platform x86 the JIT ASM looks like it doesn’t optimize whereas for target platform x64 the JIT ASM looks like it does. However, I haven’t checked that in details yet. I encourage to get the C# code and put it on the sharplab.io!

Have a nice day, bye!