Tail recursion

Tail recursion is a special kind of recursion in a program. It is also a special kind of [tail call]?. Tail recursion is used in Functional programming languages to fit a recursive function into an iterative process.

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 procedure which would 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

tail recursion and [tail call]?s in general take far less space because no state save for the calling function's address needs to be saved, neither on the stack nor on the heap.