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