Tail call

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. For tail calls, there is no need to remember the caller – instead, tail-call elimination makes only the minimum necessary changes to the stack frame before passing it on,[4] and the tail-called function will return directly to the original caller. 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,[5][6] and languages in the ML family among others. 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.

A tail call can be located just before the syntactical end of a function:

function foo(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:

function bar(data) {
    if ( a(data) ) {
        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.

In this code:

function foo1(data) {
    return a(data) + 1;
}

function foo2(data) {
    var ret = a(data);
    return ret;
}

function foo3(data) {
    var 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.

The following program is an example in Scheme:[8]

;; 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:

;; 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. 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.

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:

% 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

% 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]
 ).

% 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)
 ).

typedef struct list {
    void *value;
    struct list *next;
} list;

list *duplicate(const list *ls)
{
    list *head = NULL;

    if (ls != NULL) {
        list *p = duplicate(ls->next);
        head = malloc(sizeof *head);
        head->value = ls->value;
        head->next = p;
    }
    return head;
}

;; in Scheme,
(define (duplicate ls)
  (if (not (null? ls))
    (cons (car ls)
          (duplicate (cdr ls)))
    '()))

%% in Prolog,
duplicate([X|Xs],R):-
  duplicate(Xs,Ys),
  R=[X|Ys].
duplicate([],[]).

typedef struct list {
    void *value;
    struct list *next;
} list;
void duplicate_aux(const list *ls, list *end);

list *duplicate(const list *ls)
{  
    list head;

    duplicate_aux(ls, &head);
    return head.next;
}

void duplicate_aux(const list *ls, list *end)
{
    if (ls != NULL) {
        end->next = malloc(sizeof *end);
        end->next->value = ls->value;
        duplicate_aux(ls->next, end->next);
    } else {
        end->next = NULL;
    }
}

;; in Scheme,
(define (duplicate ls)
  (let ((head (list 1)))
    (let dup ((ls  ls)
              (end head))
      (cond
        ((not (null? ls))
         (set-cdr! end (list (car ls)))
         (dup (cdr ls) (cdr end)))))
    (cdr head)))

%% in Prolog,
duplicate([X|Xs],R):-
   R=[X|Ys],
   duplicate(Xs,Ys).
duplicate([],[]).

typedef struct list {
    void *value;
    struct list *next;
} list;

list *duplicate(const list *ls)
{
    list head, *end;
    end = &head;
    while (ls != NULL)
    {
        end->next        = malloc(sizeof *end);
        end->next->value = ls->value;
        ls = ls->next;
        end = end->next;
    }
    end->next = NULL;
    return head.next;
}

 ;; in Scheme,
 (define (duplicate ls)
   (let ((head (list 1)))
     (do ((end head (cdr end))
          (ls  ls   (cdr ls )))
         ((null? ls) (cdr head))
       (set-cdr! end (list (car ls))))))

%% in Prolog,
%% N/A

In a paper delivered to the ACM conference in Seattle in 1977, Guy L. Steele summarized the debate over the GOTO and structured programming, and observed that procedure calls in the tail position of a procedure can be best treated as a direct transfer of control to the called procedure, typically eliminating unnecessary stack manipulation operations.[2] Since such "tail calls" are very common in Lisp, a language where procedure calls are ubiquitous, this form of optimization considerably reduces the cost of a procedure call compared to other implementations. Steele argued that poorly-implemented procedure calls had led to an artificial perception that the GOTO was cheap compared to the procedure call. Steele further argued that "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", with the machine code stack manipulation instructions "considered an optimization (rather than vice versa!)".[2] Steele cited evidence that well-optimized numerical algorithms in Lisp could execute faster than code produced by then-available commercial Fortran compilers because the cost of a procedure call in Lisp was much lower. In Scheme, a Lisp dialect developed by Steele with Gerald Jay Sussman, tail-call elimination is guaranteed to be implemented in any interpreter.[11]

Tail recursion is important to some high-level languages, especially functional and logic 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 calls are to be optimized so as not to grow the stack. Tail calls can be made explicitly in Perl, with a variant of the "goto" statement that takes a function name: goto &NAME;[12]

However, for language implementations which store function arguments and local variables on a call stack (which is the default implementation for many languages, at least on systems with a hardware stack, such as the x86), implementing generalized tail-call optimization (including mutual tail recursion) presents an issue: if the size of the callee's activation record is different from that of the caller, then additional cleanup or resizing of the stack frame may be required. For these cases, optimizing tail recursion remains trivial, but general tail-call optimization may be harder to implement efficiently.

For example, in the Java virtual machine (JVM), tail-recursive calls can be eliminated (as this reuses the existing call stack), but general tail calls cannot be (as this changes the call stack).[13][14] As a result, functional languages such as Scala that target the JVM can efficiently implement direct tail recursion, but not mutual tail recursion.

The GCC, LLVM/Clang, and Intel compiler suites perform tail-call optimization for C and other languages at higher optimization levels or when the -foptimize-sibling-calls option is passed.[15][16][17] Though the given language syntax may not explicitly support it, the compiler can make this optimization whenever it can determine that the return types for the caller and callee are equivalent, and that the argument types passed to both function are either the same, or require the same amount of total storage space on the call stack.[18]

Various implementation methods are available.

 foo:
  call B
  call A
  ret

 foo:
  call B
  jmp  A

function foo(data1, data2)
   B(data1)
   return A(data2)

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   push reg            ; put data2 on stack where A expects it
   call A              ; A uses data2
   pop                 ; remove data2 from stack.
   ret

 foo:
   mov  reg,[sp+data1] ; fetch data1 from stack (sp) parameter into a scratch register.
   push reg            ; put data1 on stack where B expects it
   call B              ; B uses data1
   pop                 ; remove data1 from stack
   mov  reg,[sp+data2] ; fetch data2 from stack (sp) parameter into a scratch register.
   mov  [sp+data1],reg ; put data2 where A expects it
   jmp  A              ; A uses data2 and returns immediately to caller.

Tail recursion can be related to the while statement, an explicit iteration, for instance by transforming

procedure foo(x)
    if p(x)
        return bar(x)
    else
        return foo(baz(x))

into

procedure foo(x)
    while true
        if p(x)
            return bar(x)
        else
            x ← baz(x)

where x may be a tuple involving more than one variable: if so, care must be taken in implementing the assignment statement x ← baz(x) so that dependencies are respected. One may need to introduce auxiliary variables or use a swap construct.

More generally,

procedure foo(x)
    if p(x)
        return bar(x)
    else if q(x)
        return baz(x)
    ...
    else if r(x)
        return foo(qux(x))
    ...
    else
        return foo(quux(x))

can be transformed into

procedure foo(x)
    while true
        if p(x)
            return bar(x)
        else if q(x)
            return baz(x)
        ...
        else if r(x)
            x ← qux(x)
        ...
        else
            x ← quux(x)

For instance, this Julia program gives a non-tail recursive definition fact of the factorial:

function factorial(n)
    if n == 0
        return 1
    else
        return n * factorial(n - 1)
    end
end

Indeed, n * factorial(n - 1) wraps the call to factorial. But it can be transformed into a tail-recursive definition by adding an argument a called an accumulator.[8]

This Julia program gives a tail-recursive definition fact_iter of the factorial:

function factorial(n::Integer, a::Integer)
    if n == 0:
        return a
    else
        return factorial(n - 1, n * a)
    end
end

function factorial(n::Integer)
    return factorial(n, 1)
end

This Julia program gives an iterative definition fact_iter of the factorial:

function fact_iter(n::Integer, a::Integer)
    while n > 0
        a = n * a
        n = n - 1
    end
    return a
end

function factorial(n::Integer)
    return fact_iter(n, one(n))
end

• Clojure – Clojure has recur special form.[22]
• Common Lisp – Some implementations perform tail-call optimization during compilation if optimizing for speed
• Elixir – Elixir implements tail-call optimization,[23] as do all languages currently targeting the BEAM VM.
• Elm – Yes[24]
• Erlang – Yes
• F# – F# implements TCO by default where possible [25]
• Go – No support[26]
• Haskell – Yes[27]
• JavaScript – ECMAScript 6.0 compliant engines should have tail calls[28] which is now implemented on Safari/WebKit[29] but rejected by V8 and SpiderMonkey
• Kotlin – Has tailrec modifier for functions[30]
• Lua – Tail recursion is required by the language definition[31]
• Objective-C – Compiler optimizes tail calls when -O1 (or higher) option specified but it is easily disturbed by calls added by Automatic Reference Counting (ARC).
• OCaml – Yes
• Perl – Explicit with a variant of the "goto" statement that takes a function name: goto &NAME;[32]
• PureScript – Yes
• Python – Stock Python implementations do not perform tail-call optimization, though a third-party module is available to do this.[33] Language inventor Guido van Rossum contends that stack traces are altered by tail-call elimination making debugging harder, and prefers that programmers use explicit iteration instead[34]
• Racket – Yes[35]
• Ruby – Yes, but disabled by default [36]
• Rust – tail-call optimization may be done in limited circumstances, but is not guaranteed[37]
• Scala – Tail-recursive functions are automatically optimized by the compiler. Such functions can also optionally be marked with a @tailrec annotation, which makes it a compilation error if the function is not tail recursive[38]
• Scheme – Required by the language definition[39][40]
• Tcl – Since Tcl 8.6, Tcl has a tailcall command[41]
• Zig – Yes[42]

Look up tail recursion in Wiktionary, the free dictionary.

• Course-of-values recursion
• Recursion (computer science)
• Primitive recursive function
• Inline expansion
• Leaf subroutine
• Corecursion