Why languages such as C, Pascal cannot implement tail recursion?

Question

I'm reading SICP. It is mentioned in one of the footnote that:

Making a compiler generate tail-recursive code might seem like a straightforward idea. But most compilers for common languages, including C and Pascal, do not do this, and therefore these languages cannot represent iterative processes in terms of procedure call alone. The difficulty with tail recursion in these languages is that their implementations use the stack to store procedure arguments and local variables as well as return addresses.

---

I'm unable to understand why it is not possible to implement tail recursion if stack is used for procedure arguments, local variables and return addresses.

Answer 1

C certainly can implement tail recursion. Tail recursion in C looks like this:

int foo (int bar)
{
    int baz;
    ...
    return foo(baz);
}

All C compilers can do that. Some (indeed most) of them provide optimization for it so it doesn't use additional stack space, like this (gcc, MSVC and clang/LLVM):

• How do I check if gcc is performing tail-recursion optimization?
• Which, if any, C++ compilers do tail-recursion optimization?
• http://llvm.org/docs/CodeGenerator.html#tail-call-optimization

I don't know much about Pascal, but here is a reference to a non-LLVM based pascal compiler supporting tail recursion in 2004:

• http://en.wikipedia.org/wiki/Free_Pascal#Consolidation:_the_2.2.x_release_series

Given the LLVM case works with multiple languages and is probably the most common modern compiler back end, and given those are the most common C compilers, and given your source appears not to distinguish between tail recursion and tail recursion without using stack space, I'd suggest your source is either wrong or at best out of date.

Re the second part of your question:

I'm unable to understand why it is not possible to implement tail recursion if stack is used for procedure arguments, local variables and return addresses.

It is possible to implement tail recursion using the stack, just like any other recursion. However, if you don't optimize it so not to use the stack (per e.g. the links above), then deep recursion will cause you to run out of stack space. Arguably in a modern environment where memory is cheap and ones stack size is not constrained by a 32-bit memory map, this is less of a problem. However, given most compilers do optimize and can avoid the stack anyway, it works in other more challenging environments too.

Answer 2

The difficulty with tail recursion in these languages is that their implementations use the stack to store procedure arguments and local variables as well as return addresses.

In machine language, there are no function calls, so function calls are translated into

1. Push the arguments into the call stack
2. push the return address into the stack
3. goto the body of the subroutine you want to call
4. when the subroutine exits, it goes back to the return address we pushed to the stack earlier
5. arguments get removed from the stack

Now there are two basic variations of this "calling convention" pattern, having to do with who is responsible for step 5 (removing function arguments from the stack). In C, the calling convention is that the function caller is responsible for cleaning the stack. This allows for variadic functions like printf (in these cases only the caller knows the correct number of arguments to pop after the call completes) but means that you can't do tail call optimization since "returning" is not the last thing a function does (you still need to clean the stack afterwards). On the other hand, if your calling convention is to have the function itself clean up the stack then you lose the ability to have variadic functions but can have TCO.