Geeks With Blogs
Jason Whitehorn MarshalByRefObject.net
UPDATE (12/17/2007): My blog has moved. This post is now located at: http://jason.whitehorn.ws/2006/06/10/Tail-Recursion.aspx




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 {
.entrypoint
.maxstack 8
tail. //this is the only things that makes it "proper"
call void main()
ret
}


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. Posted on Friday, June 9, 2006 1:54 AM .NET | Back to top


Comments on this post: Tail Recursion

Comments are closed.
Comments have been closed on this topic.
Copyright © Jason Whitehorn | Powered by: GeeksWithBlogs.net