Reputation: 1416
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.
Upvotes: 22
Views: 5550
Reputation: 10663
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.
Upvotes: 30
Reputation: 183
Well, the two are somehow related −as they both have the word 'tail' in them− but are completely differents…
Tail recursion is a recursion with some specific constraints, and tails calls are function calls. Your question is a bit like "what is the difference between an animal and a cat?"…
A tail call is a function call in tail position.
Examples: f(x)
in f(x)
, and g(★)
in g(f(x))
Counter-examples: f(x)
in 1+f(x)
and in g(f(x))
Tail recursion is a recursion where recursive calls are tail calls.
Examples: f(★)
on the right of the "=" sign in f(x) = f(x)
, f(x,y) = if x == 0 then y else f(x-1,y+x)
I have defined two recursive functions that call themselves with tail calls. That's it.
In languages with TCO, tail calls cost nothing, so (tail) recursion works in constant stack, and everyone is happy.
Upvotes: 3
Reputation: 36118
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.
Upvotes: 16