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