What Is Tail Call Optimization?

Question

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?

Answer 1

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.

Answer 2

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, so here are two examples of the factorial function in Scheme:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

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:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

In contrast, the stack trace for the tail recursive factorial looks as follows:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

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.

Answer 3

There's some code on http://en.wikipedia.org/wiki/Tail_recursion, along with an explanation that I couldn't do better here.

Answer 4

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.

Answer 5

TCO (Tail Call Optimization) is the process by which a smart compiler can make a call to a function 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 that 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:

def fact(n):
    if n == 0: return 1
return n * fact(n-1)

Since this does things besides call another function in its return statement. This version is TCOptimizable:

def fact_h(n, acc):
    if n == 0: return acc
    return fact_h(n-1, acc*n)

def fact(n): return fact_h(n, 1)

This is because the last thing to happen in any of these functions is to call another function.

Answer 6

It's a very simple thing. Theory is already explained before here. I am writing for more experiments here.

You can even do it if your compiler doesn't support it. Just write two programs to workout factorials and compare the time needed.

One is the regular recursive way. Another is another recursive way but you won't return the value, rather save in a global variable. It is safe because only one function call is active and it will always go from lowest end to the highest.

Here is the algorithm (I am not writing in perfect C):

int globalReturnVal;

int GetFactorial(int n)
{
   if(n>1)
   {
      GetFactorial(n-1);
      globalReturnVal=globalReturnVal*n;
   }
}

int main()
{
   GetFactorial(10);
   //print globalReturnVal now ;).
}

Wrote it quickly. May have bugs in the code, but not in the logic