Alex Rivera | Logout

What is difference between tail calls and tail recursion?

Asked 2012-08-20T21:15:24.627
23

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.

lisp scheme
Edit
Report

1 Answer

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.

answered 2012-09-06T02:01:29.483

Your Answer