Tail recursion - Revision history

Karl Jones at 13:50, 5 October 2016

2016-10-05T13:50:43Z

Karl Jones at 13:50, 5 October 2016

2016-10-05T13:50:12Z

Karl Jones at 13:48, 5 October 2016

2016-10-05T13:48:11Z

Karl Jones: Created page with "In computer science, a '''tail call''' is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being calle..."

2016-10-05T13:45:06Z

Created page with "In computer science, a '''tail call''' is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being calle..."

New page

In [[computer science]], a '''tail call''' is a [[subroutine]] call performed as the final action of a procedure.

If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of [[recursion]]. Tail recursion (or tail-end recursion) is particularly useful, and often easy to handle in implementations.

== Description ==

Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements, thus allowing efficient structured programming.

In the words of Guy L. Steele, "in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as <nowiki>[machine code]</nowiki> JUMP instructions."

Traditionally, tail call elimination is optional. However, in functional programming languages, tail call elimination is often guaranteed by the language standard, allowing tail recursion to use a similar amount of memory as an equivalent loop. The special case of tail recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language semantics do not explicitly support general tail calls, a compiler can often still optimize sibling calls, or tail calls to functions which take and return the same types as the caller.

== See also ==

== External links ==

* [https://en.wikipedia.org/wiki/Tail_call Tail recursion] @ Wikipedia

[[Category:Computer science]]
[[Category:Recursion]]

@@ Line 7: / Line 7: @@
 Tail calls can be implemented without adding a new [[stack frame]] to the [[call stack]]. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as [[Goto|GOTO statements]], thus allowing efficient [[structured programming]].
-In the words of [[Guy L. Steele]], "in general, procedure calls may be usefully thought of as [[Goto|GOTO statements]] which also pass [[Parameter (computer programming)
+In the words of [[Guy L. Steele]], "in general, procedure calls may be usefully thought of as [[Goto|GOTO statements]] which also pass [[Parameter (computer programming)|parameters]], and can be uniformly coded as <nowiki>[machine code]</nowiki> JUMP instructions."
-From Wikipedia, the free encyclopedia|parameters]], and can be uniformly coded as <nowiki>[machine code]</nowiki> JUMP instructions."
 Traditionally, tail call elimination is optional. However, in functional programming languages, tail call elimination is often guaranteed by the language standard, allowing tail recursion to use a similar amount of memory as an equivalent loop. The special case of tail recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language semantics do not explicitly support general tail calls, a compiler can often still optimize sibling calls, or tail calls to functions which take and return the same types as the caller.

@@ Line 5: / Line 5: @@
 == Description ==
-Tail calls can be implemented without adding a new [[stack frame]] to the [[call stack]]. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements, thus allowing efficient [[structured programming]].
+Tail calls can be implemented without adding a new [[stack frame]] to the [[call stack]]. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as [[Goto|GOTO statements]], thus allowing efficient [[structured programming]].
-In the words of [[Guy L. Steele]], "in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as <nowiki>[machine code]</nowiki> JUMP instructions."
+In the words of [[Guy L. Steele]], "in general, procedure calls may be usefully thought of as [[Goto|GOTO statements]] which also pass [[Parameter (computer programming)
 Traditionally, tail call elimination is optional. However, in functional programming languages, tail call elimination is often guaranteed by the language standard, allowing tail recursion to use a similar amount of memory as an equivalent loop. The special case of tail recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language semantics do not explicitly support general tail calls, a compiler can often still optimize sibling calls, or tail calls to functions which take and return the same types as the caller.

@@ Line 1: / Line 1: @@
 In [[computer science]], a '''tail call''' is a [[subroutine]] call performed as the final action of a procedure.
-If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of [[recursion]]. Tail recursion (or tail-end recursion) is particularly useful, and often easy to handle in implementations.
+If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of [[Recursion (computer science)|recursion]]. Tail recursion (or tail-end recursion) is particularly useful, and often easy to handle in implementations.
 == Description ==
-Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements, thus allowing efficient structured programming.
+Tail calls can be implemented without adding a new [[stack frame]] to the [[call stack]]. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements, thus allowing efficient [[structured programming]].
-In the words of Guy L. Steele, "in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as <nowiki>[machine code]</nowiki> JUMP instructions."
+In the words of [[Guy L. Steele]], "in general, procedure calls may be usefully thought of as GOTO statements which also pass parameters, and can be uniformly coded as <nowiki>[machine code]</nowiki> JUMP instructions."
 Traditionally, tail call elimination is optional. However, in functional programming languages, tail call elimination is often guaranteed by the language standard, allowing tail recursion to use a similar amount of memory as an equivalent loop. The special case of tail recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls. When the language semantics do not explicitly support general tail calls, a compiler can often still optimize sibling calls, or tail calls to functions which take and return the same types as the caller.
 == See also ==
 == External links ==