>>18,19Well, he's dumb, but he isn't wrong. The function call is effectively removed and the stack frame isn't saved. Consider
(define (fact x) (if (= x 1) 1 (* x (fact (- x 1)))))
. A non-tco'd compiled code segment may look something like:
fact_non_tco:
push rbp
mov rbp, rsp
mov rax, 1
sub rsp, 8
mov [rsp], rcx
cmp rcx, 1
je .unwind
dec rcx
call fact
.unwind:
imul rax, [rsp]
add rsp, 8
leave
ret
. While non-TCO may compile too something like:
fact_tco:
mov rax, 1
.recurse:
cmp rcx, 1
je .exit
imul rax, rcx
dec rcx
jmp .recurse
.exit:
ret
. The first has to save the stack, making space complexity dependent on the size of the input, while the second does not.