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.
(define (factorial n) (define (iter n acc) (if (<= n 1) acc (iter (- n 1) (* acc n)))) (iter n 1))
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.