Menu
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?
615
Since many Scheme compilers use C as an intermediate target code, the tail recursion must be encoded in C without growing the stack, even if the C compiler does not optimize tail calls. Many implementations achieve this by using a device known as a trampoline, a piece of code that repeatedly calls functions.
Tail call optimization happens when the compiler transforms a call immediately followed by a ret into a single jmp . This transformation saves one instruction, and more importantly it eliminates the implicit push/pop from the stack done by call and ret .
This kind of function call is called a tail call, and languages like Haskell, Scala, and Scheme can avoid keeping around unnecessary stack frames in such calls. This is called tail call optimization (TCO) or tail call elimitation.
Last notes. Tail-call optimization is a part of the ES2015-ES6 specification. Supporting it isn't a NodeJS thing, it's something the V8 engine that NodeJS uses needs to support.
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.
108
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
