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. |
Take this Scheme program as an example (adapted from the LISP programming language page to a more SICP?ish style):
(define (factorial n) (define (iter n acc) (if (<= n 1) acc (iter (- n 1) (* acc n)))) (iter n 1))
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:
call fact (3) call iter (3 1) call iter (2 3) call iter (1 6) call iter (0 6) return 6 return 6 return 6 return 6 return 6
into the more space- (and time-)efficient? variant:
call fact (3) replace arguments with (3 1), jump into "iter" replace arguments with (2 3), re-iterate replace arguments with (1 6), re-iterate replace arguments with (0 6), re-iterate return 6
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.