Search code examples
cstandardstail-recursiontail-call-optimization

C tail call optimization


I often hear people say that C doesn't perform tail call elimination. Even though it's not guaranteed by the standard, isn't it performed in practice by any decent implementation anyhow? Assuming you're only targeting mature, well implemented compilers and don't care about absolute maximum portability to primitive compilers written for obscure platforms, is it reasonable to rely on tail call elimination in C?

Also, what was the rationale for leaving tail call optimization out of the standard?


Solution

  • Statements like "C doesn't perform tail call elimination" make no sense. As you correctly noted yourself, things like this depend entirely on the implementation. And yes, any decent implementation can easily turn tail-recursion into [an equivalent of] a cycle. Of course, C compilers do not normally give any guarantees about what optimizations will and what optimizations will not happen in each particular piece of code. You have to compile it and see for yourself.