Prevent Stack Overflow in Recursion

In the previous part we solved a problem using recursion. In this solution a method keeps calling itself. When a method calls a method, it has some administrative cost, it needs memory. For example, the CPU needs to know where to continue the execution of the program code after it returns from a method, so it needs to store the return address. Also, if the caller and callee method want to communicate, they need a shared memory, this is what they use to pass parameters and return values.

Execution Stack

The most common solution to provide the necessary memory for method calls is using a stack. The size of the stack is limited, however. The exact size depends on several factors – it can be set for a new thread, for example, but usually it is around 1-2Mb. To see what this size is enough for, let’s try it out through an example.

The limits of an Execution Stack

Let’s say that the problem we want to solve is to answer the question that how many times we need to add 1 to itself to get the value n. The solution of this problem cries for recursion:

  • if n=0, then the solution is 0
  • if n>0, it’s getting complicated, but it helps a lot that we know that the solution of n is greater by 1 than the solution of n-1. For example, f(10) = 1 + f(9).

Now that we have figured out how to solve a part of the problem and how we can get a smaller problem with a similar shape, we can write a recursive method:

static uint f(uint n)
{
    if (n == 0)
        return 0;
    else
        return 1 + f(n - 1);
}

Calling the method, it calculates the result for a given n:

Console.WriteLine(f(5000));

and the result is 5000. But when we want to calculate the result for 50000, what we get is:

Process is terminated due to StackOverflowException.

We can see that the stack is not big enough to support 50000 calls. My configuration provides enough space for ~37000 calls. It sounds a lot, but this example is very limited. It is a static method, so no need to pass the “this” reference, which is the hidden first parameter of every non static method. Also, it has only one parameter, and the jitter compiles a code where this single parameter is passed through a register instead of the stack. And no explicit local variables. Still the CLR allocates 64 bytes on the stack just to run this simple method.

push        ebp      ; 4 bytes
mov         ebp,esp 
push        edi      ; 4 bytes
push        esi      ; 4 bytes
push        ebx      ; 4 bytes
sub         esp,40h  ; 64 bytes
...

This 64 bytes doesn’t contain the saved registers and the return address. This simple method needs 64 + 16 bytes and the return address, 84 bytes altogether on a 32 bit system.

We can increase the length of a call chain if we allocate larger stack for a thread:

var thread = 
       new Thread( 
              _ => Console.WriteLine(f(50000)), 
              8000000); // ~ 8MB stack
 
thread.Start();
thread.Join();

In this case the method can calculate the result.

Catch me if you can

Another problem with stack overflow is that we cannot catch the exception it generates. We cannot prevent this application to crash:

try
{
    Console.WriteLine(f(300000));
}
catch
{
    Console.WriteLine("ooops..");
}

Even if we try to catch every type of exceptions, this “every” doesn’t include StackOverflowException. It is a bad news. Let’s say that we are implementing a service application, and it’s API can accept a recursive data structure. If a client sends a huge recursive data block, the service will fill up the stack processing this input, and crashes. It will stop serving not only the client who sent the poisoning data, but all the other clients being served.

Ensure Sufficient Execution Stack

The example with the service application is not just random, I discovered a possible solution of this problem browsing the source code of the model binder of MVC4. This model binder was able to read recursive data – and it would not crash if someone sent a 100000 deep tree structure. The trick it used was provided by the RuntimeHelpers class, which had gotten a new method EnsureSufficientExecutionStack() with .NET 4.
This method does what its name says: it checks that the stack has enough space to support a method call. If not, it throws its own exception instead of StackOverflowException, so we can catch it:

static uint f(uint n)
{
    if (n == 0)
    {
        return 0;
    }
    else
    {
        RuntimeHelpers.EnsureSufficientExecutionStack();
        return 1 + f(n - 1);
    }
}
 
static void Main(string[] args)
{
    try
    {
        Console.WriteLine(f(300000));
    }
    catch (InsufficientExecutionStackException)
    {
        Console.WriteLine("Out of stack space");
    }
    catch
    {
        Console.WriteLine("ooops..");
    }
}    

Now the program will not crash and we have a chance to handle the problem in a more sophisticated way.

Tech Interview – Recursive Tree Traversal

One of the improvements we need to make on the Like Statistic application is to change the structure of the database where the datafiles are stored. The database is a directory with datafiles, and the program reads all datafiles from that given directory from a single level, but doesn’t read those from the subdirectories.

DirStruct

In the MainWindow class, the following method provides the files from the database to be processed. It reads the files from a single level, the first parameter is the path to the database, the second is basically the extension of the datafiles which is determined by the selected source type, like “xml” or “bin”.

private IEnumerable<string> GetFileList()
{
    return FileSystem.GetFiles(
               this.GetDatabasePath(),
               this.GetSelectedSourceType());
}

We need to use the FileSystem class only because the .net framework Directory.GetFiles() would be able to return all files from a directory structure, and this is just too easy, we wanted the candidates working a little-bit more, so they need to find an algorithm which walks through the directory structure. The FileSystem class is a simple wrapper around the .Net framework Diretory class:

internal static class FileSystem
{
    internal static string[] GetFiles(string path, string extension)
    {
        return Directory.GetFiles(path, "*." + extension);
    }

    internal static string[] GetDirectories(string path)
    {
        return Directory.GetDirectories(path);
    }
}

We can use two simple methods from the FileSystem class, the first returns all files from a given path, and the second returns all directories from a given path.

What is recursion?

We have a directory structure, its a tree structure, and many candidates can recall that if we want to walk through a tree structure, we can use recursion. But when I ask about what recursion is, the most common answer is that its when a method calls itself.

This answer is kind of ok, but there is a better way to think about recursion. The fact that a method calls itself is just a result of a problem solving strategy. When we think about recursion, it should be just a special way we solve the problem, not a way we call a method.

What is this strategy? From time to time we see problems that when we start to solve, they fall apart to more sub-problems which have the same shape than the original problem. Sometimes this happens without any effort, sometimes we need to be tricky to make the sub-problems to have the same shape.

Let’s see an example. This example is simple, still many developers have problems solving it on an interview, probably because we can solve this problem more easily without recursion. Let’s say, that we have an array:

int[] a = { 4, 6, 7, 5, 8, 2, 8 };

Now we need to write a program that increases every element in the array by one. It is simple, we just write a loop:

for (var i = 0; i < a.Length; i++)
  a[i]++;

Let’s say, that we are using a buggy c# compiler, and it cannot compile anything that is related to loops. We don’t have ‘for’, ‘while’, but we cannot trick it using ‘goto’. What we can do is to increment a given element like a[0] or a[10]:

static void Increment(int[] a)
{
  if (a.Length > 0)
    a[0]++;
  else
    return;
 
  if (a.Length > 1)
    a[1]++;
  else
    return;
 
...
 
  if (a.Length > 2345643)
    a[2345643]++;
  else
    return;
...
}

This solution has two main problems. First, it can be really long, second, we never know what the largest array is we need to be able to handle, so we don’t know what should be the last number we try.

Let’s just solve a part of the problem. The original problem is that we want to increase [a1,…,an]. First, we just solve it for [a1]

  if (a.Length > 0)
    a[0]++;

The remaining problem is to increase [a2,…,an], which is quite similar to the original problem, but smaller. How can we use this?

Let’s write the original problem a little more general way.

Given [a1,…,ak,…,an].
Our task is to increment [ak,…,an].
If k=1, then we get the original problem, which is to increment every element in the array.

Let’s solve a part of the problem, increment only ak from [ak,…,an]

static void Increment(int[] a, int k)
{
  a[k]++;
}

The remaining problem is to increment items [ak+1,…,an], which is smaller than the original problem but has exactly the same shape. Because it has exactly the same shape, we can use the method we are currently writing to solve it. That is the point of the recursion. We try to find or make sub-problems that are the same as the problem we are currently solving, because in that case we can use the currently written method to solve them. So let’s do this:

static void Increment(int[] a, int k)
{
  a[k]++;
  Increment(a, k+1);
}

We are almost done, we need to take care of one little thing, as the original problem becomes smaller and smaller, there is a point when it disappears, and we don’t catch that point in the current code, in our case the value of ‘k’ can grow too high. We need to stop when we reach the end of the array, so the final code looks like this:

static void Increment(int[] a, int k)
{
  a[k]++;

  if (k+1 < a.Length)
    Increment(a, k+1);
}

Now that we have seen how it is important to understand how a problem can be divided into similar sub-problems, lets work with the directory structure. Our problem is the following:

DbFileStruct

The blue squares are directories, and the red circles are files. The part we easily can solve is to get the red circles from the first level:

private IEnumerable<string> GetFileList(string root, string sourceType)
{
    var result = FileSystem.GetFiles(root, sourceType);
}

The remaining sub-problems have the same shape as our original problem:

DbFileStruct2

Because the sub-problems have the same shape, we can solve them using the currently written method. We can get the sub-problems – which are sub directories – using the ‘FileSystem.GetDirectories(root)’ call. We can write something like this:

private IEnumerable<string> GetFileList(string root, string sourceType)
{
    var result = FileSystem.GetFiles(root, sourceType);

    var subdirectories = FileSystem.GetDirectories(root);
    foreach (var directory in subdirectories)
    {
        var subresult = GetFileList(directory, sourceType);
        ...
    }
    ...
}

This code traverses the whole directory structure, it gets all the file names, but it doesn’t return a full file list. Somehow we need to merge the sub-results. We could create a list and load all sub-results into it, then return it back:

private IEnumerable<string> GetFileList(string root, string sourceType)
{
    var result = new List<string>();

    var subresult = FileSystem.GetFiles(root, sourceType);
    result.AddRange(subresult);

    var subdirectories = FileSystem.GetDirectories(root);
    foreach (var directory in subdirectories)
    {
        subresult = GetFileList(directory, sourceType);
        result.AddRange(subresult);
    }

    return result;
}

The drawback of this solution is that it copies lists several times. Not a performance issue in this example, but it is really simple to avoid this. Instead of merging the sub-results, why don’t we pass around a list where every call copies its sub-result into?

private void GetFileList(string root, string sourceType, IList<string> aggregateFileList)
{
    var files = FileSystem.GetFiles(root, sourceType);
    aggregateFileList.AddRange(files);

    var subdirectories = FileSystem.GetDirectories(root);
    foreach (var directory in subdirectories)
    {
        GetFileList(directory, sourceType, aggregateFileList);        
    }
}

And the original GetFileList() method can start the recursion:

IEnumerable<string> GetFileList()
{
    var result = new List<string>();
 
    GetFileList(
        this.GetDatabasePath(),
        this.GetSelectedSourceType(),
        result);
 
    return result;
}

Do we need recursion here?

A directory tree has recursive nature, but we don’t really need to use a self calling method to walk it through. Even if it is not a problem now, self-calling methods have a drawback: they store the state of the problem solving algorithm together with the method call chain. Actually, the current method call chain represents a part of the program solving state.
The problem with this is that we cannot just return to the caller method in the middle of the problem solving with the intention that we continue the process later. Doing this, we lose the state of the problem solving process.
Lets say, that we have a zillion directories to process. The current solution reads this all in a list and then returns it. We need to hold them all in the memory. In the case of zillion directories it would be better to read the files from one directory at a time, process them, then continue with the next directory. Like when we have an iterator which walks through the directory structure as we call the next() method repeatedly. We cannot do this easily when we use self calling methods.
To see that it is quite easy to implement an iterator like that if we use a different approach than recursion, we will write that code in the next part.