Tail recursion

Sponsor with the world's largest charity for orphans

Tail recursion is a method for partially transforming a recursion in a program into an iteration: it applies when the recursive calls in a function are the last executed statements in that function.

Tail recursion is used in functional programming languages to fit an iterative process into a recursive function. Functional programming languages can typically detect tail recursion and optimize the execution into an iteration which saves stack space, as described below. Since having a complete call graph is a daunting task for compilers, a mere tail call is usually referred to as being tail recursive.

Besides space and exectution efficiency, the tail recursion is important to allowing a common idiom in functional programming, continuation-passing style (CPS) without quickly running out of stack space. Since the tail recursion is so important in this portability of code, the standard for Scheme programming language requires implementations to be properly tail recursive. This means that programmers can expect the tail recursive code to be interpreted as efficiently as stack-based iterative code.

The tail expression in Scheme is defined as follows:

1. The body of a lambda expression is a tail expression.

2. If (if E₀ E₁ E₂) is a tail expression, then both E₁ and E₂ are tail expressions.

3. Nothing else is a tail expression.

Take this Scheme program as an example (adapted from the Lisp programming language page to a more SICPish style):

  (define (factorial n)

    (define (iterate n acc)

      (if (<= n 1)

acc

          (iterate (- n 1) (* acc n))))

    (iterate n 1))

As you can see, the inner procedure iterate calls itself last in the control flow. This allows an interpreter or compiler to reorganize the execution which would ordinarily look like this:

  call factorial (3)

   call iterate (3 1)

    call iterate (2 3)

     call iterate (1 6)

     return 6

    return 6

   return 6

  return 6

into the more space- (and time-) efficient variant:

  call factorial (3)

  replace arguments with (3 1), jump into "iterate"

  replace arguments with (2 3), re-iterate

  replace arguments with (1 6), re-iterate

  return 6

This reorganization saves space because no state except for the calling function's address needs to be saved, neither on the stack nor 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" (acc in the above implementation of factorial) as an argument to a 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.