Tail recursion in C# & F#
I’m currently in the process of learning functional programming using the F# programming language. It’s a slow & long journey but I enjoy it and even though I’m not using it on any real project (yet), “It makes my C# better“. While learning F#, I came across a technique called Tail-recursion … this is something most of us have learned during our studies, but I’m not sure everybody is using it on a daily basis
I wasn’t really aware of the implications this could have at runtime if the compiler could recognize tail-recursive functions and optimize code for them (basically, generate a loop) : successive recursive calls don’t consume additional stack space and thus don’t eventually cause a StackOverflow exception (looking at the Call Stack debug window in Visual Studio shows that only 1 stack frame is being used).
It is very interesting to know that the F# compiler does optimize code when it encounters tail-recursive functions while the C# compiler (most of the time) doesn’t. So, basically, there is no limitation at the CLR level, it is mostly up to the compiler to optimize or not based on some heuristics. If the C# compiler is not on par with F# one (yet), some improvements have been made in the latest release (4.0).
If you’re interested by this topic, here is a list of very informative posts (.Net specific):
- Tail recursion in C# and F#
- Adventures in F# – Tail recursion in 3 languages
- Enter, Leave, Tailcall hooks – Basics
- Enter, Leave, Tailcall hooks – Tall tales of tail calls
- Tail call improvements in .Net Framework 4
- Recursion in F# and the Tail Recursion Police
- Tail call recursion in C#
- Immutability and tail recursion
And if, like me, you are a newbie in functional programming but you are willing to learn (on the .Net platform with F#) I would recommend the following book : Programming F#



