Tail Recursion and C#

Tail recursion is a powerful optimization since it typically improves both execution time and memory usage for recursive calls. It can also be your enemy if you forget about it.

A few months ago a friend had a problem that his service over time would use more and more CPU while at the same time being unable handle as much requests as before. So the number of requests went down while CPU went up. Taking a crash dump showed that a lot of threads were executing the same code. Code that was recursive. At first this puzzled my friend since he expected any recursive call that ends up in an infinite loop to eventually run out of stack and throw an exception. Yet this didn't happen in this case.

A debug build of the service was deployed and all of a sudden in crashed with a StackOverflowException! And then it struck my friend; tail recursion! Obviously the compiler optimized the release build for tail recursion but not the debug build! And looking closer at where the service crashed he quickly found the bug that caused the recursive call to never stop calling itself.

While tail recursion is an important feature for any functional language that typically relies on recursion heavily it is often forgotten in a language like C#. And there is a lot of magic to it because just because you put your recursive call at the end your function is no guarantee for tail recursion.

Looking at various resources online I learned that the C# compiler does not emit the "tail" IL instruction which F# compiler does. Hence the tail recursion is relying on the JIT compiler to detect it. I also had to build my program for x64 in order to get tail recursion to work since "Any CPU" and x86 would not do it on my x64 machine.

So my conclusion is that you should never rely on tail recursion working or not working in your C# program because there are just too many reasons it will not. That means you need to keep your call depth shallow and in the case of recursion being used you cannot rely on a stack overflow to save you; you need your own guard against infinite recursion.