22

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.

7
  • 8
    I'm not sure I understand the question. Didn't you already explain the difference between tail calls and tail recursion yourself? As you said, tail recursion is if the tail call calls the function itself while just "tail call" can be a call to any function. So that's the difference.
    – sepp2k
    Commented Aug 20, 2012 at 21:19
  • exactly. en.wikipedia.org/wiki/Tail_call Commented Aug 20, 2012 at 21:21
  • 3
    That simple? I suspect that there could be some more substantial difference, or I am wrong?
    – jjpcondor
    Commented Aug 20, 2012 at 21:34
  • 2
    mutual recursion can be tail recursion too, when mutually recursive functions call each other (not just each one - itself) always in tail position. Also, it's only about stack. Other resources can be consumed or not, what characterizes the TCO is constant stack usage.
    – Will Ness
    Commented Aug 21, 2012 at 9:15
  • 6
    I have a dream that some day people will stop EVER using the term "tail recursion" and only use "tail call". The concept of tail call elimination has nothing to do with recursion. Tail call elimination is just easiest to implement for tail self-calls, but makes sense for any calls whatsoever, as Andreas pointed out.
    – jkff
    Commented Aug 31, 2012 at 1:10

3 Answers 3

29

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.

7
  • 1
    great answer! I'd just really like to see some elaboration on what exactly did you mean by "just handling tail-recursive functions specially is not enough to achieve proper tail recursion". What does this refer to?
    – Will Ness
    Commented Aug 21, 2012 at 9:21
  • @WillNess, see Andreas's answer, which talks about this and gives links for more details. Commented Aug 21, 2012 at 14:33
  • one more thing. Is the old stack frame really that useless? If "tail call is a jump that passes arguments", where does it passes them? On the old stack frame, is it not? (at least when it calls itself). I think TCO is as much about stack frame reuse as direct jumps. In case of say three mutually recursive functions the three frames might coexist in the stack, too. Looks like TCO is about recovering the forsaken GOTO of unstructured programming. :)
    – Will Ness
    Commented Sep 8, 2012 at 12:45
  • @Will, for most tail calls, caller and callee are not the same, and likely have stack frames of different size and layout. You may not even know the callee at compile time. Hence, you cannot simply "reuse stack frames", except in the special case of statically known self tail calls, i.e. tail recursion (where you rather want to transform into a loop anyway). Commented Sep 8, 2012 at 14:29
  • Also, in "whose" stack frame arguments are passed depends on the calling convention. If the callee is supposed to remove its arguments from the stack (as is the case on a number of platforms), then a caller has to do so before a tail call, and before putting the new arguments on the stack, at least conceptually. Commented Sep 8, 2012 at 14:30
16

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.

3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.