A Practical Introduction to Tail Recursion

May 1, 2021

You are likely already familiar with the concept of recursion—the notion of breaking larger problems into a collection of smaller, more managable problems and then solving them iteratively—though the concept of tail recursion might be more alien. It is, fortunately, relatively straightforward!

Consider, for instance, this implementation of map in Scheme:

(define (mymap fnc lst)
    (if (null? lst)
        '()
        (cons (fnc (car lst)) 
              (mymap fnc (cdr lst)))))

If lst is empty, we immediately return the empty list ’(). However, if lst is not empty, we need to construct an actual result. Accordingly, we cons, or construct, a new list in which fnc has been applied to every element of our input list lst. We achieve this by calling the function on the first element of our list, and then recursively cons-ing that together with the result of calling mymap once more with the same function and the remainder of our list. This is the call seen in the last line.

However, in this implementation, before we can even cons the very first element of our list, we necessarily need to compute the value of all subsequent elements. This is true throughout the entire list. In other words: The first actual cons-ing can only occur once we have iterated through the entire list. Surely we can do better?

Suppose, instead, we built our result as we iterated through our input?

Consider this implementation:

(define (myMapTail fnc lst)
    (myMapTailHelper fnc lst '()))

(define (myMapTailHelper fnc lst acc)
    (if (null? lst)
        acc
        (myMapTailHelper fnc (cdr lst) (cons (fnc (car lst)) acc))))

Now, because we are using the helper-function myMapTailHelper, which we instantiate with the same function, the same list, and the empty list, we can return the accumulator acc once our list is empty. Moreover, this time around, the first thing which happens is the recursive call.

We handle whatever logic needs to be handled on each parameter: (cdr lst) takes the remainder of the list, and (cons (fnc (car lst)) acc) constructs our accumulator. Indeed, since acc is a list—remember, we instantitate it with ’()—we can continuously cons additional elements to it. This is also what enables us to return acc once our input list is empty.

This is tail recursion.

We are not quite done with the above example, however. Since we construct our result—that is, our accumulator—element by element as we iterate through our input list, our accumulator ends up being reversed:

> (define lst (list 1 2 3 4 5))
> (define fnc (lambda (x) (* 2 x)))
> (myMap fnc lst)
(2 4 6 8 10)
> (myMapTail fnc lst)
(10 8 6 4 2)

We thus update our myMapTail implementation as follows:

(define (myMapTail fnc lst)
    (reverse (myMapTailHelper fnc lst '())))

The result is now how it should be:

> (myMapTail fnc lst)
(2 4 6 8 10)

Applying the same logic, we can create our own tail recursive filter:

(define (myFilter fnc lst)
  (reverse (myFilterHelper fnc lst '())))

(define (myFilterHelper fnc lst res)
  (if (null? lst)
      res
      (if (fnc (car lst))
          (myFilterHelper fnc (cdr lst) (cons (car lst) res))
          (myFilterHelper fnc (cdr lst) res))))

Of course, it needs to be stressed that while tail recursion is neat, it cannot be leveraged in any setting and very much depends on both the specific requirements—e.g. general efficiency and memory consumption—your particular project may have in addition to the chosen programming language. However, if you do happen to be working in a Lisp-like language, tail recursion fast becomes relevant.