# Stack memory usage for tail calls

I'm puzzled by this statement from Wikipedia:

For tail calls, there is no need to remember the place we are calling from — instead, we can perform tail call elimination by leaving the stack alone (except possibly for function arguments and local variables [my emphasis]) [...]

I thought that the amount of space for a tail call was constant. I thought that it was O(1), not O(n) where n would be the depth of the stack (if it were not tail-recursive). But what is this "(except possibly for function arguments and local variables)"?

Is memory usage for a tail call not constant and can you get a memory overflow?

-
Interestingly, defining tail recursion formally is somewhat tricky and rarely done. See W. D. Clinger, Proper Tail Recursion and Space Efficiency. –  Martin Berger Jul 29 '11 at 12:00

Is memory usage for a tail call not constant and can you get a memory overflow?

The stack usage for tail-recursive functions is bounded by a constant (i.e., is $O(1)$). However, you may still need to manipulate the stack at each recursive call in order to ensure that arguments are where the procedure expects them to be. Here's an example of such a program, written in Ocaml.

let rec frob n a b c d e f g =
if n = 0 then
a
else
frob (n-1) b c d e f g a

What this does is take decrement a counter, and rotate its arguments until it reaches 0. This program will compile to the following machine code:

_camlFrob__frob_1030:
subl    $28, %esp L101: movl %eax, 0(%esp) movl %ebx, 24(%esp) movl _caml_extra_params + 0, %ebp movl _caml_extra_params + 4, %ebx movl 0(%esp), %eax cmpl$1, %eax
jne     L100
movl    24(%esp), %eax
addl    28, %esp ret .align 16 L100: movl %ebx, 20(%esp) movl %ebp, 16(%esp) movl %edi, 12(%esp) movl %esi, 8(%esp) movl %edx, 4(%esp) movl %ecx, 0(%esp) addl-2, %eax
movl    0(%esp), %ebx
movl    4(%esp), %ecx
movl    8(%esp), %edx
movl    12(%esp), %esi
movl    16(%esp), %edi
movl    20(%esp), %ebp
movl    %ebp, _caml_extra_params + 0
movl    24(%esp), %ebp
movl    %ebp, _caml_extra_params + 4
jmp     L101

As you can see, it is not pushing anything on the stack (the contents of %esp), but it does need to shuffle the contents of the stack around before making the tail call (jmp L101). (As an aside, decrementing the n variable is accomplished by subtracting 2 from %eax, since Ocaml uses a tagged representation of integers.)

I seem to recall that the problem of putting variables into slots so as to minimize the amount of stack/register shuffling you need to do is NP-complete, and that consequently most compilers rely on heuristics to figure out what to do.

(P.S. I don't know what's wrong with the indentation -- it's fine in the preview....)

-

I do not think that the part of Wikipedia you quoted is talking about space complexity. It simply states that unlike non-tail calls, tail calls do not have to store the return addresses in the stack. However, it is not correct to state that tail calls do not touch the stack at all, because you still have to clean up local variables allocated on the stack and possibly push arguments passed to the function onto the stack, hence the parenthesized note.

-