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?
Stack memory usage for tail calls
recursion
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 aWhat 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, %espL101:    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     L101As 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....)