Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 38 ยท Functions and Closures

Recursion and Tail Calls

Think recursively in Common Lisp: base cases, recursing on lists and trees, accumulators, tail calls and what SBCL does with them, mutual recursion with labels, and memoization.

Recursion, a function that calls itself, is the natural way to process Lisp's recursive data: a list is either empty or a head followed by a smaller list. This lesson teaches the recipe (base case plus smaller problem), applies it to numbers, lists and trees, introduces tail calls and accumulators, and explains when to prefer a loop. It finishes by closing Chapter 4 with a summary of how functions work in Common Lisp.

The recipe

Every recursive function has two parts:

  1. Base case: a simple input that is answered directly.
  2. Recursive case: reduce the problem to a smaller one, call yourself, and combine.
LISP
(defun factorial (n)
  (if (<= n 1)
      1                          ; base case
      (* n (factorial (- n 1))))) ; smaller problem

(factorial 5)     ; => 120
(factorial 20)    ; => 2432902008176640000
(factorial 30)    ; => 265252859812191058636308480000000   (bignums, no overflow)

Trace (factorial 3): it becomes (* 3 (factorial 2)), then (* 3 (* 2 (factorial 1))), then (* 3 (* 2 1)) which is 6. The pending multiplications wait on the call stack.

flowchart TD
    A["(factorial 3)"] --> B["(* 3 (factorial 2))"]
    B --> C["(* 3 (* 2 (factorial 1)))"]
    C --> D["(* 3 (* 2 1))"]
    D --> E["(* 3 2)"]
    E --> F["6"]

Each call waits for the smaller call to finish, then multiplies.

Recursing on lists

A list is NIL (empty) or a cons whose cdr is a smaller list. That structure suggests the template:

LISP
(defun my-length (list)
  (if (null list)
      0
      (1+ (my-length (cdr list)))))

(defun sum-list (list)
  (if (null list)
      0
      (+ (car list) (sum-list (cdr list)))))

(defun my-reverse (list)
  (if (null list)
      '()
      (append (my-reverse (cdr list)) (list (car list)))))

(sum-list '(1 2 3 4))      ; => 10
(my-reverse '(a b c))      ; => (C B A)

my-reverse works but is slow: append copies on every step, making it quadratic. We will fix that with an accumulator below.

Here is recursion running on the Mini-Lisp, a JavaScript stand-in interpreter (not SBCL):

JS Mini-Lisp: recursion on numbers and lists

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Trees

For nested lists (trees), recurse on both the car and the cdr:

LISP
(defun count-atoms (tree)
  (cond ((null tree) 0)
        ((atom tree) 1)
        (t (+ (count-atoms (car tree))
              (count-atoms (cdr tree))))))

(count-atoms '(a (b c) ((d) e)))     ; => 5

(defun flatten (tree)
  (cond ((null tree) '())
        ((atom tree) (list tree))
        (t (append (flatten (car tree))
                   (flatten (cdr tree))))))

(flatten '(1 (2 (3 4)) 5))           ; => (1 2 3 4 5)

cond with null first, atom second and a general case last is the standard shape for tree functions.

Accumulators and tail calls

A call is a tail call when it is the last thing the function does: nothing is left to combine afterwards. (1+ (my-length ...)) is not a tail call because the 1+ still has to run. To make it one, carry the answer-so-far in an accumulator parameter:

LISP
(defun my-length-2 (list)
  (labels ((walk (rest acc)
             (if (null rest)
                 acc
                 (walk (cdr rest) (1+ acc)))))   ; tail call
    (walk list 0)))

(defun my-reverse-2 (list)
  (labels ((walk (rest acc)
             (if (null rest)
                 acc
                 (walk (cdr rest) (cons (car rest) acc)))))
    (walk list '())))

(my-reverse-2 '(a b c))      ; => (C B A), in one linear pass

The accumulator version of reverse does exactly one cons per element, so it is linear and also clearly shows how reverse works.

What SBCL does with tail calls

If a tail call can reuse the caller's stack frame, a compiler can turn it into a jump, avoiding stack growth. The ANSI standard does not require this, but SBCL (and most good implementations) perform tail-call merging when code is compiled with the default optimization settings (roughly, when debug is not set high). That means my-length-2 can run on a list of a million elements without a deep stack.

Non-tail recursion still uses the stack. A deep non-tail recursion eventually fails:

LISP
(my-length (make-list 1000000))
;; may print: Control stack exhausted (no more space for function call frames)
;; SBCL then offers the usual debugger restarts

Rules for portable code:

  • Do not rely on tail-call elimination when depth is unbounded, since another implementation or a debug setting may keep frames.
  • For simple counting loops, prefer loop, dotimes or do, which are guaranteed constant-space.
  • Use recursion where the data is recursive (trees, nested structures) and its depth is small.

Since JavaScript engines do not merge tail calls, this stand-in (plain JS, not Lisp) uses a trampoline to show the idea of running a tail-recursive function in constant stack:

JS Stand-in: tail recursion with a trampoline

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Mutual recursion

Two functions can call each other; define them together with labels:

LISP
(defun parity (n)
  (labels ((even? (k) (if (= k 0) t   (odd?  (1- k))))
           (odd?  (k) (if (= k 0) nil (even? (1- k)))))
    (if (even? n) :even :odd)))

(parity 10)    ; => :EVEN
(parity 7)     ; => :ODD

Fibonacci and the cost of naive recursion

LISP
(defun fib (n)
  (if (< n 2)
      n
      (+ (fib (- n 1)) (fib (- n 2)))))

(fib 10)     ; => 55
(fib 35)     ; works but takes noticeable time: ~30 million calls

Each call spawns two more, so the work roughly doubles with n. Two cures:

LISP
;; 1. An accumulating helper: linear time
(defun fib-fast (n)
  (labels ((walk (i a b)
             (if (= i n) a (walk (1+ i) b (+ a b)))))
    (walk 0 0 1)))

;; 2. Memoization with a hash table (see Closures and Lexical Scope)
(let ((cache (make-hash-table)))
  (defun fib-memo (n)
    (or (gethash n cache)
        (setf (gethash n cache)
              (if (< n 2) n (+ (fib-memo (- n 1)) (fib-memo (- n 2))))))))

(fib-fast 90)    ; => 2880067194370816120
(fib-memo 100)   ; => 354224848179261915075

Memoization is explained in Closures and Lexical Scope.

Debugging recursion

trace prints every call and return, which is the fastest way to see what a recursive function does:

LISP
(trace sum-list)
(sum-list '(1 2 3))
(untrace sum-list)

If you hit "Control stack exhausted", look for a missing or unreachable base case first, then for non-tail recursion over a huge input.

Chapter wrap-up

You now know how Common Lisp functions work end to end: lambda lists with &optional, &key and &rest; multiple values; functions as values with #', funcall and apply; closures that keep private state; and recursion that mirrors recursive data. The rest of the course builds on these, starting with macros, where the code-is-data idea pays off.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the two required parts of a recursive function?

    Without a base case it never stops; without a smaller problem it never progresses.
  2. 2. Which is a tail call?

    A tail call is the last action; nothing remains to be done with its result.
  3. 3. Does the ANSI standard guarantee tail-call elimination?

    It is an implementation feature; for unbounded depth prefer loop constructs.
  4. 4. What shape should a function over nested lists (trees) follow?

    Trees can nest in both the head and the tail.
  5. 5. Why is naive recursive Fibonacci slow?

    Each call spawns two more; use an accumulator or memoization.

Summary

  • A recursive function needs a base case and a call on a smaller input; lists and trees fit this naturally.
  • Template for lists: (if (null list) base (combine (car list) (f (cdr list)))); for trees recurse on both car and cdr.
  • Accumulator parameters turn recursion into tail calls and avoid quadratic append.
  • SBCL merges tail calls in compiled code, but the standard does not require it; prefer loops for unbounded iteration.
  • Use labels for helper and mutually recursive functions; memoize or use accumulators to fix exponential recursion.

Next: Macros: Code as Data in Common Lisp