Editing Tail call (section)

{{Short description|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.<ref name="MuchnickAssociates1997">{{cite book|author1=Steven Muchnick|author2=Muchnick and Associates|title=Advanced Compiler Design Implementation|url=https://archive.org/details/advancedcompiler00much|url-access=registration|date=15 August 1997|publisher=Morgan Kaufmann|isbn=978-1-55860-320-2}}</ref> 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 (computer science)|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 [[Exec (system call)|overlay]] for processes, but for function calls). The program can then [[jump (computer science)|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."<ref name="aim-443" />

Not all programming languages require tail-call elimination. However, in [[functional programming language]]s, tail-call elimination is often guaranteed by the [[Programming language specification|language standard]], allowing tail recursion to use a similar amount of memory as an equivalent [[loop (computing)|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.<ref name="llvm.org">{{cite web|url=http://llvm.org/docs/CodeGenerator.html#sibling-call-optimization|title=The LLVM Target-Independent Code Generator — LLVM 7 documentation|website=llvm.org}}</ref>