I suspect you think about recursion in terms of a call stack, yes? So when you have tail recursion, you're still pushing a frame onto the stack by default, unle

I suspect you think about recursion in terms of a call stack, yes? So when you have tail recursion, you're still pushing a frame onto the stack by default, unless the compiler recognizes that it can optimize that way. Yes? The traditional FP model of computation doesn't have a call stack. It proceeds by reduction: replace one subexpression with another, in the program text itself, and repeat until you can't do it anymore. So if I've got a fibonacci function in two clauses, `fib 0 a b = b` and `fib n a b = fib (n - 1) b (a + b)`, then a reduction may look like this: fib 3 0 1 -- initial program = fib 2 1 (0 + 1) -- substitute second clause of `fib` = fib 2 1 1 -- evaluate `+` = fib 1 1 (1 + 1) = fib 1 1 2 = fib 0 2 (1 + 2) = fib 0 2 3 = 3 -- substitute first clause of `fib` Notice how the tail-recursion naturally falls out of the substitution steps performed by the interpreter. There are no stack frames; the whole "rest of the program" (which is what a call stack is) is just the program itself. This isn't just an analogy; this is the way computation works in an FP. To an FP system, the call stack is the invisible, behind-the-scenes optimization.