In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function is a recursive call. Such recursions can be easily transformed to iterations. Replacing recursion with iteration, either manually or automatically, can drastically decrease the amount of stack space used and improve efficiency. This technique is commonly used with functional programming languages, where the declarative approach and explicit handling of state promote the use of recursive functions that would otherwise rapidly fill the call stack. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... This article is about the concept of recursion. ... The word iteration is sometimes used in everyday English with a meaning virtually identical to repetition. ... In computer science, a call stack is a special stack which stores information about the active subroutines of a computer program. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. ... Declarative programming is a term with two distinct meanings, both of which are in current use. ... In information processing, a state is the complete set of properties (for example, its energy level, etc. ... In computer science, a call stack is a special stack which stores information about the active subroutines of a computer program. ...

Description

When a function is called, the computer must "remember" the place it was called from, the return address, so that it can return to that location with the result once the call is complete. Typically, this information is saved on the stack, a simple list of return locations in order of the times that the call locations they describe were reached. Sometimes, the last thing that a function does after completing all other operations is to simply call a function, possibly itself, and return its result. But in this case, there is no need to remember the place we are calling from — instead, we can leave the stack alone, and the newly called function will return its result directly to the original caller. Converting a call to a branch or jump in such a case is called a tail call optimization. Note that the tail call doesn't have to appear lexically after all other statements in the source code; it is only important that its result be immediately returned, since the calling function will never get a chance to do anything after the call if the optimization is performed. In both conventional and electronic messaging, a return address is an explicit inclusion of the address of the person sending the message. ...

For normal, non-recursive function calls, this is usually a micro-optimization that saves little time and space, since there are not that many different functions available to call. When dealing with recursive or mutually recursive functions, however, the stack space and the number of returns saved can grow to huge numbers, since a function can call itself, directly or indirectly, a huge number of times. In fact, it often asymptotically reduces stack space requirements from linear, or O(n), to constant, or O(1). The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

If several functions are mutually recursive, meaning they each call one another, and each call they make to one another in an execution sequence uses a tail call, then tail call optimization will give a properly tail recursive implementation that does not consume stack space. Proper tail recursion optimization is required by the standard definitions of some programming languages, such as Scheme. Scheme is a multi-paradigm programming language. ...

The notion of tail position in Scheme can be defined as follows:

1. The body of a lambda expression is in tail position.
2. If (if E₀ E₁ E₂) is in tail position, then both E₁ and E₂ are in tail position.

Examples

Take this Scheme program as an example: Scheme is a multi-paradigm programming language. ...

 (define (factorial n) (define (fac-times n acc) (if (= n 0) acc (fac-times (- n 1) (* acc n)))) (if (< n 0) (display "Wrong argument!") (fac-times n 1))) 

As you can see, the inner procedure fac-times calls itself last in the control flow. This allows an interpreter or compiler to reorganize the execution which would ordinarily look like this: An interpreter is a computer program that executes other programs. ... A diagram of the operation of a typical multi-language, multi-target compiler. ...

 call factorial (3) call fac-times (3 1) call fac-times (2 3) call fac-times (1 6) call fac-times (0 6) return 6 return 6 return 6 return 6 return 6 

into the more space- (and time-) efficient variant: In computer science, efficiency is used to describe several desirable properties of an algorithm or other construct, besides clean design, functionality, etc. ...

 call factorial (3) replace arguments with (3 1), jump to "fac-times" replace arguments with (2 3), jump to "fac-times" replace arguments with (1 6), jump to "fac-times" replace arguments with (0 6), jump to "fac-times" return 6 

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. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions.

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 (acc 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.^{[citation needed]}

Besides space and execution efficiency, tail recursion optimization is important in the functional programming idiom known as continuation passing style (CPS), which would otherwise quickly run out of stack space. Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. ... Continuation passing style (CPS) is a term used within functional programming to describe a style of programming wherein functions never return. ...

Tail recursion modulo cons

Tail recursion modulo cons is a generalization of tail recursion introduced by David H. D. Warren. As the name suggests, the only operation needed after the recursive call is a cons, which adds a new element to the front of the list that was returned. The optimization moves this operation inside the recursive call by creating a list node with the front element, and passing a reference to this node as an argument. This article discusses the usage of the term modulo as a form of mathematical jargon. ... CONS, Connection-Oriented Network Service, is one of the two OSI stack network layer protocols, the other being CLNS (Connectionless Network Service). ... David H. D. Warren is a computer scientist (Ph. ...

For example, consider a function that duplicates a linked list, described here in C: C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...

 list *duplicate(const list *input) { if (input == NULL) { return NULL; } else { list *head = malloc(sizeof *head); head->value = input->value; head->next = duplicate(input->next); return head; } }  

In this form the function is not tail-recursive, because control returns to the caller after the recursive call to set the value of head->next. But on resumption, the caller merely prepends a value to the result from the callee. So the function is tail-recursive, save for a "cons" action, that is, tail recursive modulo cons. Warren's method gives the following purely tail-recursive implementation:

 list *duplicate(const list *input) { list *head; duplicate_prime(input, &head); return head; } void duplicate_prime(const list *input, list **p) { if (input == NULL) { *p = NULL; } else { *p = malloc(sizeof **p); (*p)->value = input->value; duplicate_prime(input->next, &(*p)->next); } }  

Note how the callee now appends to the end of the list, rather than have the caller prepend to the beginning.

The properly tail-recursive implementation can be converted to iterative form:

 list *duplicate(const list *input) { list *head; list **p = &head; while (input != NULL) { *p = malloc(sizeof **p); (*p)->value = input->value; input = input->next; p = &(*p)->next; } *p = NULL; return head; }  

Implementation methods

Tail recursion is important to some high-level languages, especially functional languages and members of the 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 operations 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: goto &NAME; A high-level programming language is a programming language that, in comparison to low-level programming languages, may be more abstract, easier to use, or more portable across platforms. ... Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ... Wikibooks has a book on the topic of Perl Programming Perl is a dynamic programming language created by Larry Wall and first released in 1987. ...

Since many Scheme compilers use 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, 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. Scheme is a multi-paradigm programming language. ... C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... In computer programming, the word trampoline has a number of meanings, associated with jumps. ...

Using a trampoline for all function calls is rather more expensive than the normal C function call, so at least one Scheme compiler, Chicken, uses a technique first described by Henry Baker from an unpublished suggestion by Andrew Appel,^[1] in which normal C 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."^[1] The garbage collection ensures that mutual tail recursion can continue indefinitely. Chicken is a compiler and interpreter for the Scheme programming language that compiles Scheme code to standard C. It is mostly R5RS compliant and offers many extensions to the standard. ... Henry Baker is the name of a computer scientist who has made contributions in such areas as Garbage collection and the Actor model. ... As of 2004, Andrew W. Appel is a professor of computer science at Princeton University. ... Cheneys algorithm, first described in a 1970 ACM paper by C.J. Cheney, is a method of garbage collection in computer software systems. ...

See also

• Course-of-values recursion

In computability theory, course-of-values recursion is a technique for defining number-theoretic functions by recursion. ...

References

Look up tail recursion in Wiktionary, the free dictionary.

• D. H. D. Warren, DAI Research Report 141, University of Edinburgh, 1980.

1. ^ ^{a b} Henry Baker, "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A."

This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL. Wikipedia does not have an article with this exact name. ... Wiktionary (a portmanteau of wiki and dictionary) is a multilingual, Web-based project to create a free content dictionary, available in over 150 languages. ... Year 1980 (MCMLXXX) was a leap year starting on Tuesday (link displays the 1980 Gregorian calendar). ... This article does not cite any references or sources. ... “GFDL” redirects here. ...