Tail recursion is a special kind of recursion in a program. It is also a special kind of [tail call]?. Tail recursion is used in Functional programming languages to fit a recursive function into an iterative process. |
Tail recursion is a special kind of recursion in a program; it occurs when the recursive calls in a function are the last executed statements in that function. Tail recursion is used in functional programming languages to fit an interative process into a recursive function. Functional programming languages can typically detect tail recursion and optimize the execution, as described below. |
As you can see, the inner procedure "iter" calls itself last in the control flow. This allows an interpreter or compiler to re-organize the procedure which would look like this: |
As you can see, the inner procedure "iter" calls itself last in the control flow. This allows an interpreter or compiler to re-organize the execution which would ordinarily look like this: |
tail recursion and [tail call]?s in general take far less space because no state save for the calling function's address needs to be saved, neither on the stack nor on the heap. |
This reorganization saves space because no state except for the calling function's address needs to be saved, neither on the stack nor on the heap. |