37

Possible Duplicate:
Why doesn't .net/C# eliminate tail recursion?

Does C# do tail recusion?

I can't find any documentation telling me if it does or not.

Community
  • 1
  • 1
Vilor
  • 371
  • 1
  • 3
  • 3
  • 2
    see this post http://stackoverflow.com/questions/491376/why-doesnt-net-c-eliminate-tail-recursion – Ashley John Aug 18 '11 at 04:52
  • 2
    also this from msdn http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-jit-conditions.aspx – Ashley John Aug 18 '11 at 04:53
  • The C# Specification does not mention TCO. –  Aug 18 '11 at 04:54
  • I believe it to be related more to the compiler than the language – V4Vendetta Aug 18 '11 at 04:58
  • @V4Vendetta Not so. A compiler (and run-time) just implements a language (perhaps with bugs, extensions, and clever optimizations). Without guarantees provided by the language it is an infuriating exercise to try guess what the compiler/run-time/JIT will do in a given situation (and what it will do in a *slightly different* environment). –  Aug 18 '11 at 05:04

2 Answers2

14

C# does not innately support tail recursion in the language but here is an interesting article on a similar technique call trampolining that may help you in your situation

Chris McGrath
  • 1,727
  • 3
  • 19
  • 45
6

Unfortunately, it does not, at least not yet.

I'm not sure if the standard itself specifies anything about (dis)allowing tail recursion. Regardless, since .Net supports tail recursion, so it would be nice for this to make its way into C#.

If you really need tail recursion in a .Net language, consider F# as an alternative.

Ken Wayne VanderLinde
  • 18,915
  • 3
  • 47
  • 72
  • 1
    It (.NET) does. Both 32- and 64-bit JITters have done it since CLR 2, but it has been vastly improved in .NET 4. – porges Aug 18 '11 at 05:05
  • I'd still like to know a good reason as to why tail recursion isn't implemented directly in the C# compiler. It seems pretty simple to do (especially considering that tail recursion is native to .Net), and it's a really useful feature that one needs to rely on sometimes (ok, not *needs* per se, but would rather not have to write out a loop instead). – Ken Wayne VanderLinde Aug 18 '11 at 06:54
  • There's a bit of a weird thing there :) With the 64-bit JITter, it's mostly irrelevant whether or not the compiler emits `tail.` prefixes for its calls. There are only a few cases where it makes a difference (main exception: it matters if you've disabled optimizations), so from the compiler's point of view, it doesn't really matter. http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-jit-conditions.aspx I'm not sure what the current behaviour of the 32-bit JITter is but according to the previous article (CLR 2) the compiler had to emit the prefix for it to take effect. – porges Aug 22 '11 at 06:02
  • @KenWayneVanderLinde Tail recursion optimization is just that---an optimization. Optimizing tail calls means the runtime is no longer able to produce correct stack traces (because some stack frames are elided by the optimization). If C# compiler optimized the tail calls, the code would then produce incorrect stack traces. Source: http://gbracha.blogspot.cz/2009/12/chased-by-ones-own-tail.html – user7610 Jul 03 '15 at 20:38
  • @user7610 Thanks a lot for that reference, I enjoyed reading it. However, it actually contradicts, rather than supports, your statements. You claim that "Optimizing tail calls means the runtime is no longer able to produce correct stack traces", but Bracha showed exactly the opposite. He even says that tail call optimization should be required, and references Guy Steele, who makes the case that tail call optimization is required to fully support object oriented abstraction (I found Steele's article [here](http://www.eighty-twenty.org/2011/10/01/oo-tail-calls/); the original link is dead). – Ken Wayne VanderLinde Jul 03 '15 at 21:38
  • @KenWayneVanderLinde He says preserving stack traces and good debugging experience in general is a problem. He then puts forth few ideas for optimizing tail calls while keeping stack traces. Show me a language that actually implements any of it, though. Since there is none, that suggests it is not that simple. – user7610 Jul 03 '15 at 22:02
  • 2
    He is right that tall call optimization should be required, though. In fact, CLR supports tail calls exactly for the reason in his Argument 1 (at tne end of the blog). "For CLR 4 the fact that the x64 JIT would sometimes not honor the “tail.” prefix prevented functional languages like F# from being viable. So we worked to improve the x64 JIT so that it could honor the “tail.” prefix all of the time and help make F# a success." http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11/tail-call-improvements-in-net-framework-4.aspx – user7610 Jul 03 '15 at 22:04