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

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.