Tail recursion

Tail recursion is a special kind of recursion in a program; it occurs 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 interative process into a recursive function. Functional programming languages can typically detect tail recursion and optimize the execution, as described below.

Take this Scheme program as an example (adapted from the LISP programming language page to a more SICP?ish style):

   (define (factorial n)
      (define (iter n acc)
       (if (<= n 1)
         acc
         (iter (- n 1) (* acc n))))
      (iter n 1))

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

   call fact (3)
    call iter (3 1)
     call iter (2 3)
      call iter (1 6)
       call iter (0 6)
       return 6
      return 6
     return 6
    return 6
   return 6

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

   call fact (3)
   replace arguments with (3 1), jump into "iter"
   replace arguments with (2 3), re-iterate
   replace arguments with (1 6), re-iterate
   replace arguments with (0 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.