Tail recursion: Difference between revisions

Revision as of 14:08, 13 October 2008

Revision as of 14:40, 29 October 2008

Line 123:

Using a trampoline for all function calls is rather more expensive than the normal C function call, so at least one Scheme compiler, [[Chicken (Scheme implementation)|Chicken]], uses a technique first described by [[Henry Baker (computer scientist)|Henry Baker]] from an unpublished suggestion by [[Andrew Appel]],<ref name="Chicken">Henry Baker, [http://home.pipeline.com/~hbaker1/CheneyMTA.html "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A."]</ref> in which normal C&nbsp;calls are used but the stack size is checked before every call. When the stack reaches its maximum permitted size, objects on the stack are garbage-collected using the [[Cheney algorithm]] by moving all live data into a separate heap. Following this, the stack is unwound ("popped") and the program resumes from the state saved just before the garbage collection. Baker says "Appel's method avoids making a large number of small trampoline bounces by occasionally jumping off the Empire State Building."<ref name="Chicken" /> The garbage collection ensures that mutual tail recursion can continue indefinitely.

Tail recursion is also used frequently in [[XQuery]] for traversing collections and XML documents.

==See also==