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

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.