Why is Garbage Collection Required for Tail Call Optimization?

Question

Why is garbage collection required for tail call optimization? Is it because if you allocate memory in a function which you then want to do a tail call on, there'd be no way to do the tail call and regain that memory? (So the stack would have to be saved so that, after the tail call, the memory could be reclaimed.)

Answer 1

Where did you hear that?

Even C compilers without any kind of garbage collector are able to optimize tail recursive calls to their iterative equivalent.

Answer 2

Garbage collection is not required for tail-call optimization.

Any variables allocated on the call stack will be reused in the recursive call, so there's no memory leak there.

Any local variables allocated on the heap and not freed before a tail call will leak memory whether or not tail-call optimization is used. Local variables allocated on the heap and freed before the tail call will not leak memory regardless of whether or not tail-call optimization is used.

Answer 3

It's true, garbage collection is not really required for tail-call optimization.

However, let's say you have 1 GB of RAM and you want to filter a 900MB list of integers to keep only the positive ones. Assume about half are positive, half are negative.

In a language with GC, you just write the function. GC will occur a bunch of times, and you'll end up with a 450 MB list. The code will look like this:

list *result = filter(make900MBlist(), funcptr);

make900MBlist will be incrementally GCd as the parts filter has gone through are no longer referenced by anything.

In a language without GC, to preserve tail-recursion, you'd have to do something like this:

list *srclist = make900MBlist();
list *result = filter(srclist, funcptr);
freelist(srclist);

This will end up having to use 900MB + 450MB before finally freeing the srclist, so the program will run out of memory and fail.

If you write your own filter_reclaim, that frees the input list as its no longer necessary:

list *result = filter_reclaim(make900MBlist(), funcptr);

It will no longer be tail-recursive, and you'll likely overflow your stack.

Answer 4

Like most myths, there may be a grain of truth to this one. While GC isn't required for tail call optimization, it certainly helps in a few cases. Let's say you have something like this in C++:

int foo(int arg) {
    // Base case.

    vector<double> bar(10);
    // Populate bar, do other stuff.

    return foo(someNumber);
}

In this case, return foo(someNumber); looks like a tail call, but because you're using RAII memory management, and you have to free bar, this line would translate to a lower level as follows (in informal pseudocode):

ret = foo(someNumber);
free(bar);
return ret;

If you have GC, it is not necessary for the compiler to insert instructions to free bar. Therefore, this function can be optimized to a tail call.