Tail recursion

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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