Examples of what tail-recursion is and how to avoid call stack overflow.

So far, as an iOS developer, I’ve had very little access to the call stack beyond what I learned in college. Most of the applications I do are not very resource-intensive. I’ve worked on complex applications, but that complexity is mostly about providing a good user experience.

For the past two years, as part of my PhD research, I’ve been working on a Swift application that analyzes source code history. With very large applications and long source code histories, I sometimes run into problems where my tool crashes due to a segmentation failure. I didn’t figure out what the problem was at the time, but knew that’s what happens when the data to analyze gets too big. I’ll come back to that later.

While working on projects for C and assembly programming courses, I stumbled upon tail-recursive optimization and decided to give it a try in Swift.

What is tail-recursion?

A recursive function is a function that calls itself, such as the one below that prints out all numbers from n to 0.

A tail-recursive function is a recursive function whose call to itself is at the end of the function, as shown in the following example.

These functions print numbers in reverse order, but otherwise have the same function: print all numbers between n and 0.

What does that matter?

Let’s compile these programs and run them. These programs can be compiled by call.

xcrun swiftc -O tail.swift -oresult

You can then run these programs by calling the following command

./result

Let’s try a small n (n=3).

Now let’s try a large n (n=10000).

Here we look again at segment faults. This only happens in programs that are recursively tailless. Why does this happen? What is a segment failure and why does only one program crash? To answer these questions, I’ll start with the call stack.

What is a call stack?

When a method in the program is called, it is added to the call stack. When another method is called within this method, it is also added to the call stack. When a method returns, it is removed from the call stack.

Thus, repeated method calls from recursive functions are added to the call stack until the stop condition is satisfied and the last method call returns.

What is a segment fault?

The call stack is stored in a stack memory segment. The memory layout is shown on the left.

When too many method calls are added to the call stack, the limited memory allocated to the call stack becomes full and memory locations outside the call stack are overwritten. First is the heap, then uninitialized memory, initialized memory, and finally the text segment.

An attempt to write a text segment results in a segmentation failure and program execution is stopped. It’s a security mechanism.

Tail recursive optimization.

Swift uses tail-recursive optimization, which means that if the method call in a recursive function is at the end of the function, the compiler can use jump statements instead of the method call. This means that calls to itself in recursion are not added to the call stack.

When we decompiled the previous two programs with Hopper, we saw that the assembly code for each program was very different.

The assembly code produced by a program with recursive functions is shown below. As you can see, there is a method call to iself in the _$s4main4test2nySi_tF method.

On the other hand, programs with tail recursion are optimized. As you can see, there is a jump (JG) directive here, rather than a method call.

I’ve always enjoyed writing recursive functions, but I’ve never considered the possible drawbacks of using them. Of course, the above example should be written in a loop, but it’s still a good example of how easy it is to accidentally overflow the call stack.

I now know why my source code analysis tool crashed when handling very large applications, and I will work hard to optimize the code to prevent it from happening in the future.

Rule of thumb

  • If possible, it is best to use loops rather than recursions.
  • When writing recursive functions, if possible, write the call to itself at the end of the method.