Very simply, what is tail-call optimization? More specifically, Can anyone show some small code snippets where it could be applied, and where not, with an explanation of why?
Join them; it only takes a minute:
|
|
Tail-call optimization is where you are able to avoid allocating a new stack frame for a function because the calling function will simply return the value that it gets from the called function. The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space. Scheme is one of the few programming languages that guarantee in the spec that any implementation must provide this optimization (JavaScript will also, once ES6 is finalized), so here are two examples of the factorial function in Scheme:
The first function is not tail recursive because when the recursive call is made, the function needs to keep track of the multiplication it needs to do with the result after the call returns. As such, the stack looks as follows:
In contrast, the stack trace for the tail recursive factorial looks as follows:
As you can see, we only need to keep track of the same amount of data for every call to fact-tail because we are simply returning the value we get right through to the top. This means that even if I were to call (fact 1000000), I need only the same amount of space as (fact 3). This is not the case with the non-tail-recursive fact, and as such large values may cause a stack overflow. |
|||||||||||||||||||||
|
|
Let's walk through a simple example: the factorial function implemented in C. We start with the obvious recursive definition
A function ends with a tail call if the last operation before the function returns is another function call. If this call invokes the same function, it is tail-recursive. Even though
ie the last operation is the multiplication and not the function call. However, it's possible to rewrite
Now, why is this useful? Because we immediately return after the tail call, we can discard the previous stackframe before invoking the function in tail position, or, in case of recursive functions, reuse the stackframe as-is. The tail-call optimization transforms our recursive code into
This can be inlined into
which is equivalent to
As we can see here, a sufficiently advanced optimizer can replace tail-recursion with iteration, which is far more efficient as you avoid function call overhead and only use a constant amount of stack space. |
|||||||||||||||||||||
|
|
TCO (Tail Call Optimization) is the process by which a smart compiler can make a call to a function and take no additional stack space. The only situation in which this happens is if the last instruction executed in a function f is a call to a function g (Note: g can be f). The key here is that f no longer needs stack space - it simply calls g and then returns whatever g would return. In this case the optimization can be made that g just runs and returns whatever value it would have to the thing that called f. This optimization can make recursive calls take constant stack space, rather than explode. Example: this factorial function is not TCOptimizable:
This function does things besides call another function in its return statement. This below function is TCOptimizable:
This is because the last thing to happen in any of these functions is to call another function. |
|||||||||||||||||||||
|
|
Probably the best high level description I have found for tail calls, recursive tail calls and tail call optimization is the blog post "What the heck is: A tail call" by Dan Sugalski. On tail call optimization he writes:
And on tail recursion:
So that this:
gets quietly turned into:
What I like about this description is how succinct and easy it is to grasp for those coming from an imperative language background (C, C++, Java) |
|||||||||||||||||||||
|
|
Note first of all that not all languages support it. TCO applys to a special case of recursion. The gist of it is, if the last thing you do in a function is call itself (e.g. it is calling itself from the "tail" position), this can be optimized by the compiler to act like iteration instead of standard recursion. You see, normally during recursion, the runtime needs to keep track of all the recursive calls, so that when one returns it can resume at the previous call and so on. (Try manually writing out the result of a recursive call to get a visual idea of how this works.) Keeping track of all the calls takes up space, which gets significant when the function calls itself a lot. But with TCO, it can just say "go back to the beginning, only this time change the parameter values to these new ones." It can do that because nothing after the recursive call refers to those values. |
|||||||||||||||||
|
|
Look here: http://tratt.net/laurie/tech_articles/articles/tail_call_optimization As you probably know, recursive function calls can wreak havoc on a stack; it is easy to quickly run out of stack space. Tail call optimization is way by which you can create a recursive style algorithm that uses constant stack space, therefore it does not grow and grow and you get stack errors. |
|||
|
|
|
|||||||||||||||||||||
|
protected by Srikar Appal Aug 4 '13 at 15:27
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?