Tail recursion

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.

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.