What is difference between tail calls and tail recursion?

Question

I understand that tail recursion, is a special case where a function makes tail calls to itself. But I do not understand how tail calls and tail recursion are different. In “properly tail recursive” language with implemented TCO (Tail Call Optimization), like Scheme, it means that tail calls and tail recursion do not consume stack or other resources. In a language where compiler can not optimize tail recursion, program can run out of stack and crash. In “properly tail recursive” languages, implementing tail recursion for looping is no less efficient, than using a loop, I presume.

Answer 1

Let's disambiguate "tail calls" first.

A call in tail position is a function call whose result is immediately returned as the value of the enclosing function. Tail position is a static property.

A call in tail position can be implemented without pushing anything onto the stack, because the old stack frame is essentially useless (under assumptions that are generally true in functional languages but not necessarily in C, etc). As Guy Steele put it, a tail call is a jump that passes arguments.

Roughly, a language implementation is properly tail recursive if it has the same asymptotic space usage as one that implements all calls in tail position as jumps without stack growth. That's a really rough simplification. If you want the full story, see Clinger's Proper Tail Recursion and Space Efficiency.

Note that just handling tail-recursive functions specially is not enough to achieve proper tail recursion (any tail call must be specially handled). The terminology is somewhat misleading.

Also note that there are other ways to achieve that asymptotic space efficiency without implementing tail calls as jumps. For example, you might implement them as normal calls and then periodically compact the stack by removing useless frames (somehow). See Baker's Cheney on the MTA.

Answer 2

As you say, tail recursion is a special case of a tail call. Consequently, any language that implements general TCO trivially is "properly tail recursive".

The inverse, however, does not hold. There are quite a few languages that only optimise tail recursion, because that is significantly easier -- you can translate it away into a loop directly, and don't need a specific "tail call" operation that manipulates the stack in new ways. For example, that is the reason why languages compiling to the JVM, which doesn't have a tail call instruction, typically only optimise tail (self) recursion. (There are techniques to work around the lack of such an instruction, e.g. trampolines, but they are quite expensive.)

Full tail call optimization does not only apply to self (or mutually) recursive calls, but to any calls in tail position. In particular, it extends to calls whose target is not statically known, e.g. when invoking a first-class function or a dynamically-dispatched method! Consequently, it requires somewhat more elaborate (though well-known) implementation techniques.

Many functional programming techniques -- but also some popular OO patterns (see e.g. Felleisen's ECOOP'04 presentation or Guy Steele's blog post) -- require full TCO to actually be usable.