Tail recursion: Difference between revisions

Revision as of 22:26, 16 July 2010

Revision as of 00:14, 23 July 2010

Line 129:

==Implementation methods==

Tail recursion is important to some [[high-level programming language|high-level languages]], especially functional languages and members of the [[Lisp programming language|Lisp]] family. In these languages, tail recursion is the most commonly used way (and sometimes the only way available) of implementing iteration. The language specification of Scheme requires that tail-recursive operationscalls are to be optimized so as not to grow the stack. Tail calls can also be used in [[Perl]], with a variant of the "goto" statement that takes a function name: <code>goto &NAME;</code>

Since many [[Scheme (programming language)|Scheme]] compilers use [[C (programming language)|C]] as an intermediate target code, the problem comes down to coding tail recursion in C without growing the stack. Many implementations achieve this by using a device known as a [[Trampoline (computers)|trampoline]], a piece of code that repeatedly calls functions. All functions are entered via the trampoline. When a function has to call another, instead of calling it directly it returns the address of the function to be called, the arguments to be used, and so on, to the trampoline. This ensures that the C stack does not grow and iteration can continue indefinitely.