Stack memory usage for tail calls

Question

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?

Answer 1

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....)

Answer 2

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.