Unruly Recursion and the TailCall attribute

In this post, we have a look a drawback of recursion, and how the F# compiler can help you mitigate them

We're hiring Software Developers

This post is part of our F# 8 series, in which we'll be digging into a few of the best features in the latest version of the language.

One of the core principles of functional programming is immutability by default. Gone are the days of 'why is this value all of a sudden different than what it was before?'. As a result, things that are traditionally done in loops are generally done with recursive functions.

The problem of recursive code

Let's take a look at one of these recursive functions, that calculates the length of a list:

let rec length input =
match input with
| _ :: tail -> length (tail) + 1
| [] -> 0

This seems like a pretty innocent piece of code, but let's see what happens if we call it with a large input:

> length [0..999999];;
Stack overflow.
Repeat 9638 times:
...

That's no good! As with any other function, the first call to a recursive function can only finish once all other recursive calls are finished; we get a stack overflow.

Using tail recursion to avoid stack overflows

One way of avoiding this is by making your functions tail recursive. You make sure that there are no operations that take place after the recursive function call. In itself, this does not solve the problem, but the F# compiler uses tail call optimalization to convert these functions into regular loops. A common way of making your functions tail recursive is passing in an accumulator.

let rec length input acc =
match input with
| _ :: tail -> length tail (acc + 1)
| [] -> acc

If we run it with the same argument that we used for the non-tail recursive function, we don't run into issues:

> length2 [0..999999] 0;;
val it: int = 1000000

In fact, we never will!

The TailCall attribute

But how do we ensure we don't actually write non-tail recursive code that will lead to stack overflows in production? Introducing the [<TailCall>]> compiler attribute! Add this to a function, and you'll be notified if it is not tail recursive. If you add it to the first iteration of our reverse function, you'll get the following warning:

 warning FS3569: The member or function 'reverse' has the 'TailCallAttribute' attribute, but is not being used in a tail recursive way.

This is a brand new F# 8 feature. You can read all about how this feature came to life on the Microsoft .Net blog

An uncovered case

While writing this post, I noticed that, when using the TailCall attribute, the compiler would not warn me of all cases where a recursive call is not in the tail position. The following function would not trigger a warning, but is not tail recursive, and can still lead to stack overflows:

let rec reverse (input: list<'t>) =
match input with
| [] -> []