Recursion without Stack Overflows

This can look like a hard achievement, but actually it isn’t. We’ll use F# language and a technique called Tail Recursion.

Recursion itself is a little bit scary for a lot of developers, but there’s no reason to that, it’s just a repetition loop with another outfit.

Eventually you will need it, so, it’s better to be prepared.

As I said before, recursion is a repetition loop technique, so, it’ll help you to solve problems that can be decomposed into smaller problems.

However, there are some issues around using recursion. In general, a recursive loop is slower than a regular loop. In addition to that, there’s a major limitation called call stack.

The call stack

Before we start to code, let’s understanding what the call stack is. Well, this data structure is used by our program to store a pointer to an execution line.

This storage procedure occurs every time your program call a function (any function, not just the recursive ones), this way, the program will be able to return to the correct execution line after function execution.

Let’s see how it works by create a simple hello function:

You should set a breakpoint at line 2 and open the Call Stack Window, this way, you’ll be able to check the call stack, as you can see below:

The call stack is a very useful structure for our programs, however, it may be the reason for a crash in our application. In fact, there’s an extremely popular exception raised by the call stack: StackOverflow.

Have you ever seen that name? — You probably already have seen it at stackoverflow forum, it’s just a joke, because as I said before, it’s a extremely popular exception, mainly when you are learning about recursion.

This exception occurs because there’s a fixed memory dedicated to the call stack, it can be different depending on the language, but usually it’s around 1MB.

Then, if we call functions enough to overflow it, bang! We got a StackOverflow exception.

A recursive sum

Let’s create a recursive function that sums all elements of a given list:

This is a simple pattern matching that returns zero if the list is empty [] , or otherwise it will return the sum of the head element (first element of the list) and the sum of the tail (all other elements of the list).

Let’s create a 1000 elements list and call this function:

Yay, success!

Now, let’s increase the list size to 10000:

Ooops, it doesn’t looks like a success right now. We just got a StackOverflow exception.

It happens because we aren’t using tail recursion yet. Ok, I got it, but after all, what tail recursion is?

Tail Recursion and the Tail Call

Tail recursion is a specific type of recursion implemented by some languages (mainly the functional programming languages). This concept is directly related to what we call as tail call.

A tail call is when a function call occurs with the guarantee that there’s no instructions to be executed after it. It should be the last instruction at all.

So, because the call is the last thing to happen, is pretty fair to say that the instruction line to return after this new call is the same instruction line to the previous call, because there’s no code to be executed after this tail call.

Because of that, the program doesn’t need to store a pointer to each call, because it’s all the same. Internally the compiler will replace this recursive tail call with a JUMP instruction, it’ll avoid the overflow exception and improve performance as well, it’s a win win deal.

Now, we need to understanding why our code isn’t using a tail call. Well, a tail call only happens when the function call is at a tail position. Tail position is just the name of the last instruction of a function, it may be a lot of different things, let’s see some examples:

Hold on a second, the function4 isn’t the same structure of our previous code? — No, it isn’t.

It’s almost the same, in fact each branch of an pattern matching can be a tail position, however, there’s an extra code on our pattern branch.

We aren’t simply return a value, we are making a sum between a value and the result of a function call. As you probably know, the function call occurs before the sum itself, so, the call isn’t the last instruction.

Are you already figured out how to solve it?

It’s pretty simple, instead to accumulate the value with returns, we’ll accumulate the value as a parameter. So, our function now contains two different parameters: the list and the accumulator.

To prevent the function consumer to give a wrong value as accumulator, we gonna make this new function a nested function, and call it internally always passing zero as accumulator initial value.

Maybe this code looks a little more unfamiliar to you, but it’s ok, tail recursion is very important (and useful) when we are talking about functional programming, as recursive functions is preferred over regular loops.

So, let’s check our code again:

No StackOverflow at all!

In fact, we can set a breakpoint to check the call stack:

As we can see, there’s no new pointers added in each call! How cool is that?

Now we implemented a tail recursion properly, but how can I check if my new random function was implemented correctly?

Well, the simplest test ever is just execute your function with a very large input, another simple test is check the call stack. But of course, there’s a more accurated test.

IL Disassembler

You can use the IL Disassembler in order to make a more deep analysis.

If you don’t know IL at all, I strongly recomend you to check this link. Here’s a quick overview: IL is the intermediate language generated by .NET compiler. When you compile your .NET code this is the result, which’ll be compiled again in execution time (JIT).

The IL Disassembler can be open by Visual Studio Developer Command Prompt, you can type “developer command” at Windows search box and it’ll be listed (it looks like the regular command prompt).

You can navigate to your project folder and execute the command ildasm project-name.dll, it’ll open the IL Disassembler, as shown in the following image:

Now, let’s check the first sum function, which raised the StackOverflow exception.

Maybe the IL language looks weird to you, but this isn’t a problem, we don’t want to understanding the language in a comprehensive way right now. Let’s focus on call instruction, it happens in four different moments:

1. IL 003 — call to get_TailOrNull() function;
2. IL 011 — call to get_TailOrNull() function;
3. IL 018 — call to get_HeadOrDefault() function;
4. IL 020 — call to sum function;

The last call is the most important one, because it shows that a new call really occurs here.

Now, let’s check the tailRecursionSum function:

Oops, something is wrong, there’s also a call instruction here. Well, actually to check our recursive function we need to open the nested function.

In order to open this IL code, we need to navigate at program tree and open the Invoke file:

Now, let’s see the code:

There’s also three call instructions here. But if we look carefully we gonna see that all calls are related to head and tail functions.

Instead our last recursive call we can see a br.s instruction, which works like a JUMP to another instruction. In this specific case, a JUMP to the first instruction (IL_0000 ).

Just before this br.s we can see two starg.s instructions, this is a short for store argument, in other words, our IL code is updating the value of the arguments (acc and list), and after that, it’ll back to the first instruction with updated values, like an regular loop.

Because of this JUMP structure, there’s no Stackoverflow and there’s a performance improvement, it’s really nice to see how the things works under the hood.