return to the caller to allow it to inspect or modify the return value before returning it. Example programs The following program is an example in Scheme: ;; factorial : number -> number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))))) This is not written in a tail-recursive style, because the multiplication function ("*") is in the tail position. This can be compared to: ;; factorial : number -> number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (fact-iter 1 n)) (define (fact-iter product n) (if (= n 0) product (fact-iter (* product n) (- n 1)))) This program assumes applicative-order evaluation. The inner procedure fact-iter calls itself last in the control flow. This allows an interpreter or compiler to reorganize the execution which would ordinarily look like this: call factorial (4) call fact-iter (1 4) call fact-iter (4 3) call fact-iter (12 2) call fact-iter (24 1) return 24 return 24 return 24 return 24 return 24 into the more efficient variant, in terms of both space and time: call factorial (4) call fact-iter (1 4) replace arguments with (4 3) replace arguments with (12 2) replace arguments with (24 1) return 24 return 24 This reorganization saves space because no state except for the calling function's address needs to be saved, either on the stack or on the heap, and the call stack frame for fact-iter is reused for the intermediate results storage. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions. In typical implementations, the tail-recursive variant will be substantially faster than the other variant, but only by a constant factor. Some programmers working in functional languages will rewrite recursive code to be tail recursive so they can take advantage of this feature. This often requires addition of an "accumulator" argument (product in the above example) to the function. In some cases (such as filtering lists) and in some languages, full tail recursion may require a function that was previously purely functional to be written such that it mutates references stored in other variables. Tail recursion modulo cons Tail recursion modulo cons is a generalization of tail-recursion optimization introduced by David H.