Never rely on tail recursion elimination
Corollary: Never write a recursively method with an unbounded stack depth.
I previously posted a recursive implementation of Factorial, and asked the readers “not to bother saying it’s inefficient because of recursion, since it will probably be optimized away anyway”. Not true.
I don’t really understand why (just posted a question to StackOverflow), but C# does not generally perform tail recursion elimination (at least as my measly test show).
The following method can be easily optimized, both to work faster, consume less space and not to cause a StackOverflowException … but it is not optimized by the compiler (verified by Reflector and the fact a StackOverflowException was indeed thrown).
private static void Foo(int i) { if (i == 1000000) return; if (i % 100 == 0) Console.WriteLine(i); Foo(i+1); } |
So … if for some reason you prefer writing recursive methods over using loops, do it only where performance is not a consideration and you have a good understanding of the maximal stack depth.
