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 SICPish 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 calls 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.