Tail call - Wikipedia Jump to content Main menu Main menu move to sidebar hide Navigation Main page Contents Current events Random article About Wikipedia Contact us Contribute Help Learn to edit Community portal Recent changes Upload file Special pages Search Search Appearance Donate Create account Log in Personal tools Donate Create account Log in Contents move to sidebar hide (Top) 1 Description 2 Syntactic form 3 Example programs 4 Tail recursion modulo cons Toggle Tail recursion modulo cons subsection 4.1 Example code 4.2 C example 5 History 6 Implementation methods Toggle Implementation methods subsection 6.1 In assembly 6.2 Hardware and space complexity 6.3 Relationship to coroutines 6.4 Through trampolining 7 Relation to the while statement 8 Language support 9 See also 10 Notes 11 References Toggle the table of contents Tail call 18 languages Čeština Deutsch Español Suomi Français עברית 日本語 한국어 Lietuvių Nederlands Polski Português Русский Српски / srpski Svenska Türkçe Українська 中文 Edit links Article Talk English Read Edit View history Tools Tools move to sidebar hide Actions Read Edit View history General What links here Related changes Upload file Permanent link Page information Cite this page Get shortened URL Switch to legacy parser Print/export Download as PDF Printable version In other projects Wikidata item Appearance move to sidebar hide From Wikipedia, the free encyclopedia Subroutine call performed as final action of a procedure In computer science, a tail call is a subroutine call performed as the final action of a procedure.[1] If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recursion (or tail-end recursion) is particularly useful, and is often easy to optimize in implementations. Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is no longer needed, and 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 or tail-call optimization. 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 [machine code] JUMP instructions."[2] Not all programming languages require tail-call elimination. 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.[3] Description [edit] 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 call stack, a list of return locations in the order that the call locations were reached. In addition, compilers allocate memory for local variables of the called function and push register content (if any and/or relevant) onto the stack. Typically, it is done by allocating a stack frame including saved registers, space allocated for non-register local variables, return address and call parameters (unless they are passed in registers). For tail calls, there is no need to remember the caller or preserve content of registers – instead, tail-call elimination avoids allocation of new stack frames and makes only the minimum necessary changes to the existing stack frame before passing it on, and the tail-called function will return directly to the original caller.[4] This, however, leads to complete loss of the caller's stack frame, which is sometimes considered as a hindrance in debugging. The tail call doesn't have to appear lexically after all other statements in the source code; it is only important that the calling function return immediately after the tail call, returning the tail call's result if any, since the calling function is bypassed when the optimization is performed. For non-recursive function calls, this is usually an optimization that saves only a little time and space, since there are not that many different functions available to call. When dealing with recursive or mutually recursive functions where recursion happens through tail calls, however, the stack space and the number of returns saved can grow to be very significant, since a function can call itself, directly or indirectly, creating a new call stack frame each time. Tail-call elimination often reduces asymptotic stack space requirements from linear, or O(n), to constant, or O(1). Tail-call elimination is thus required by the standard definitions of some programming languages, such as Scheme, and languages in the ML family among others.[5][6] The Scheme language definition formalizes the intuitive notion of tail position exactly, by specifying which syntactic forms allow having results in tail context.[7] Implementations allowing an unlimited number of tail calls to be active at the same moment, thanks to tail-call elimination, can also be called 'properly tail recursive'.[5] Besides space and execution efficiency, tail-call elimination is important in the functional programming idiom known as continuation-passing style (CPS), which would otherwise quickly run out of stack space. Syntactic form [edit] A tail call can be located just before the syntactical end of a function. int a(int n); int b(int n); int foo(int data) { a(data); return b(data); } Here, both a(data) and b(data) are calls, but b is the last thing the procedure executes before returning and is thus in tail position. However, not all tail calls are necessarily located at the syntactical end of a subroutine: 0) {\n return b(data);\n }\n return c(data);\n}\n"}}'>int c(int n); int bar(int data) { if (a(data) > 0) { return b(data); } return c(data); } Here, both calls to b and c are in tail position. This is because each of them lies in the end of if-branch respectively, even though the first one is not syntactically at the end of bar's body. Consider this example: int foo1(int data) { return a(data) + 1; } int foo2(int data) { int ret = a(data); return ret; } int foo3(int data) { int ret = a(data); return (ret == 0) ? 1 : ret; } The call to a(data) is in tail position in foo2, but it is not in tail position either in foo1 or in foo3, because control must return to the caller to allow it to inspect or modify the return value before returning it. Example programs [edit] The following program is an example in Scheme:[8] number\n;; to calculate the product of all positive\n;; integers less than or equal to n.\n(define (factorial n)\n (if (= n 0)\n 1\n (* n (factorial (- n 1)))))\n"}}'>;; factorial : number -> number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1))))) This is not written in a tail-recursive style, because the multiplication function ("*") is in the tail position. This can be compared to: number\n;; to calculate the product of all positive\n;; integers less than or equal to n.\n(define (factorial n)\n (fact-iter 1 n))\n(define (fact-iter product n)\n (if (= n 0)\n product\n (fact-iter (* product n)\n (- n 1))))\n"}}'>;; factorial : number -> number ;; to calculate the product of all positive ;; integers less than or equal to n. (define (factorial n) (fact-iter 1 n)) (define (fact-iter product n) (if (= n 0) product (fact-iter (* product n) (- n 1)))) This program assumes applicative-order evaluation. The inner procedure fact-iter calls itself last in the control flow. This allows an interpreter or compiler to reorganize the execution which would ordinarily look like this:[8] call factorial (4) call fact-iter (1 4) call fact-iter (4 3) call fact-iter (12 2) call fact-iter (24 1) return 24 return 24 return 24 return 24 return 24 into the more efficient variant, in terms of both space and time: call factorial (4) call fact-iter (1 4) replace arguments with (4 3) replace arguments with (12 2) replace arguments with (24 1) return 24 return 24 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, and the call stack frame for fact-iter is reused for the intermediate results storage. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions. In typical implementations, the tail-recursive variant will be substantially faster than the other variant, but only by a constant factor. 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 (product in the above example) to the function. Tail recursion modulo cons [edit] Tail recursion modulo cons is a generalization of tail-recursion optimization introduced by David H. D. Warren[9] in the context of compilation of Prolog, seen as an explicitly set once language. It was described (though not named) by Daniel P. Friedman and David S. Wise in 1974[10] as a LISP compilation technique. As the name suggests, it applies when the only operation left to perform after a recursive call is to prepend a known value in front of the list returned from it (or to perform a constant number of simple data-constructing operations, in general). This call would thus be a tail call save for ("modulo") the said cons operation. But prefixing a value at the start of a list on exit from a recursive call is the same as appending this value at the end of the growing list on entry into the recursive call, thus building the list as a side effect, as if in an implicit accumulator parameter. The following Prolog fragment illustrates the concept: Example code [edit] % Prolog, tail recursive modulo cons: partition([], _, [], []). partition([X|Xs], Pivot, [X|Rest], Bigs) :- X @< Pivot, !, partition(Xs, Pivot, Rest, Bigs). partition([X|Xs], Pivot, Smalls, [X|Rest]) :- partition(Xs, Pivot, Smalls, Rest). -- In Haskell, guarded recursion: partition [] _ = ([],[]) partition (x:xs) p | x < p = (x:a,b) | otherwise = (a,x:b) where (a,b) = partition xs p partition(Xs,Pivot,Rest,Bigs), Smalls=[X|Rest]\n ; partition(Xs,Pivot,Smalls,Rest), Bigs=[X|Rest]\n ).\n"}}'>% Prolog, with explicit unifications: % non-tail recursive translation: partition([], _, [], []). partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs], ( X @< Pivot -> partition(Xs,Pivot,Rest,Bigs), Smalls=[X|Rest] ; partition(Xs,Pivot,Smalls,Rest), Bigs=[X|Rest] ). Smalls=[X|Rest], partition(Xs,Pivot,Rest,Bigs)\n ; Bigs=[X|Rest], partition(Xs,Pivot,Smalls,Rest)\n ).\n\n"}}'>% Prolog, with explicit unifications: % tail-recursive translation: partition([], _, [], []). partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs], ( X @< Pivot -> Smalls=[X|Rest], partition(Xs,Pivot,Rest,Bigs) ; Bigs=[X|Rest], partition(Xs,Pivot,Smalls,Rest) ). Thus in tail-recursive translation such a call is transformed into first creating a new list node and setting its first field, and then making the tail call with the pointer to the node's rest field as argument, to be filled recursively. The same effect is achieved when the recursion is guarded under a…