.NET, Archive, C#

Tail Recursion

It appears that the CLR supports proper tail recursion.
Normally when a function is called, a new frame is created on the stack. This can cause problems when too many stack entries are created, resulting in a stack overflow.
Fortunately their is an ingenious solution to this problem, called proper tail recursion. Something is tail recursive if it calls itself as the very last operation before it returns. If not implemented properly, a compiler (or run-time) will still produce stack frames, and could eventually produce an overflow.
Since the recursive call was the last thing the function performed, there is no real reason to return to it. Because of this, there is also no reason to keep the stack frames for such functions. This is exactly what happens in a proper implementation of tail recursion, the current stack frame is overwritten by the next frame. This allows for (if you desired) infinite recursion, or at least deep recursion, without the worry of a stack overflow.

This can be implemented in IL, as seen in the following example

.assembly TailRecursion {}
.method static public void main() il managed {
.maxstack 8
tail. //this is the only things that makes it "proper"
call void main()

I am not sure if the C# compiler currently supports this, but as best as I can tell it does not. I tried writing several recursive functions in C#, and then decompiled the produced EXE. In every case, the resulting IL lacked the necessary “tail.” statement to make it a proper tail recursion.

Never miss an article! Subscribe to my newsletter and I'll keep you updated with the latest content.


About Jason

Jason is an experienced entrepreneur & software developer skilled in leadership, mobile development, data synchronization, and SaaS architecture. He earned his Bachelor of Science (B.S.) in Computer Science from Arkansas State University.
View all posts by Jason →

Leave a Reply

Your email address will not be published. Required fields are marked *