Tail recursion: Difference between revisions

Revision as of 07:03, 19 February 2010

Revision as of 07:49, 19 February 2010

Line 1:

In [[computer science]], '''tail recursion''' (or '''tail-end recursion''') is a special case of [[Recursion_(computer_science)|recursion]] in which the last operation of the function, the [[tail call]], is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with [[iteration]], manually or automatically, can drastically decrease the amount of [[Call stack|stack]] space used and improve efficiency. This technique of iterative calculation is commonly used with [[functional programming]] languages, where the [[declarative programming|declarative approach]] and explicit handling of [[state (computer science)|state]] promote the use of recursive functions that would otherwise rapidly fill the [[call stack]].

==Description==

Line 13:

#''If'' (if ''E₀'' ''E₁'' ''E₂'') ''is in tail position, then both E₁ and E₂ are in tail position.''

==Examples==

SHERWIN DONATO

Take this [[Scheme (programming language)|Scheme]] program as an example:

Line 33:

;; to calculate the product of all non-negative integers

;; less than or equal to n.

(define (factorial n)

(lambda (n)
(let fact ([i n] [acc 1])

(if (zero? i)

acc

(fact (- i 1) (* acc i))))))

</source>