What is tail recursion optimization? [duplicate]

This question already has answers here: Closed 12 years ago.

Possible Duplicate:

What is tail-recursion? 开发者_StackOverflow

What is tail recursion optimization?

---

a calls b calls c calls d.

at the end you have tails:

d returns to c returns to b returns to a. if all these do nothing (like in recursion, where it is actually a calls a calls a calls a) then you can optimize that... ...into d returns to a.

---

Tail recursion does not mean that you turn a recursive call into a loop.

It means that the stack frame is no longer necessary at the point of the recursive call, and therefore may be eliminated. This can occur if the recurisive call is the last statement in the method, and if the return value of the recursive call is the return value of the current method. By eliminating the current stack frame, recursive calls may go to arbitrary depth without stack-overflow errors and with substantial savings of resources.

This optimization is normally made by the compiler/interpreter rather than the programmer.

---

In JavaScript: The Good Parts, Crockford says, "Some languages offer the tail recursion optimization. This means that if a function returns the result of invoking itself recursively, then the invocation is replaced with a loop, which can significantly speed things up."