## Encyclopedia > Tail recursion

Article Content

# 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 interative 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)
call iterate (0 6)
return 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
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. 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.

All Wikipedia text is available under the terms of the GNU Free Documentation License

Search Encyclopedia
 Search over one million articles, find something about almost anything!

Featured Article
 Bugatti ... General Motors in 1993. A luxury saloon (EB112) was planned, but never got beyond the prototype stage. The company went bankrupt in 1995. In 1998 the Bugatti name was ...