Recursion in LISP

Analogy categoryAnalogies

Why Recursion Is Central to LISP

LISP was designed around recursive list processing from the start — its very name, LISt Processing, reflects this — and its core data structure, the cons cell, naturally decomposes into a first element (car) and the rest of the list (cdr), which maps directly onto recursive thinking: process the first element, then recursively process the rest. A recursive function needs at least one base case that terminates the recursion without a further call, and one or more recursive cases that reduce the problem and call the function again, typically operating on (cdr list).

🏏

Cricket analogy: Recursion mirrors how a scorer tallies an innings: the total score is 'runs off this ball plus the score of the rest of the innings', recursively, until the base case of the last ball bowled is reached and there's nothing left to add.

lisp

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

(my-length '(a b c d))  ; => 4

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

(sum-list '(1 2 3 4 5))  ; => 15

Base Cases and Termination

Every correct recursive function must guarantee it eventually reaches a base case, or it will recurse forever and exhaust the call stack, raising a stack-overflow-style error in most implementations. For list recursion, (null lst) — checking whether the list is empty — is the most common base case test, since cdr-ing repeatedly through a proper list eventually yields nil. For numeric recursion, such as computing a factorial, the base case is typically when the counter reaches 0 or 1, as in (if (<= n 1) 1 (* n (factorial (1- n)))).

🏏

Cricket analogy: The base case is like the umpire calling 'all out' when the tenth wicket falls — no more recursive overs of bowling can happen because there's a guaranteed terminating condition built into the game's rules.

A recursive function that never reaches its base case, for example due to a typo like (cdr lst) missing from the recursive call so the same list is passed every time, will recurse indefinitely and typically signal a storage-condition or stack-overflow error rather than hang silently.

Tail Recursion and Accumulator Patterns

A recursive call is in tail position when it is the very last thing the function does — nothing further happens with its result after it returns. Many Common LISP implementations (such as SBCL) can optimize tail calls into a simple jump, reusing the current stack frame instead of growing the call stack, which prevents stack overflow on long lists. The my-length example above is not tail-recursive because (+ 1 ...) still needs to happen after the recursive call returns; rewriting it with an accumulator parameter, as in (defun my-length (lst &optional (acc 0)) (if (null lst) acc (my-length (cdr lst) (1+ acc)))), makes the recursive call the last operation performed, enabling tail-call optimization.

🏏

Cricket analogy: Tail recursion is like a relay of run-outs where the fielder throws directly to the bowler's end with nothing left to do afterward, versus a non-tail version where the fielder has to run the ball in themselves and then still relay it — the direct throw (tail call) needs no extra stack of pending actions.

Common LISP does not mandate tail-call optimization in the language standard the way Scheme does, so whether a tail-recursive function actually avoids stack growth is implementation- and optimization-setting-dependent; SBCL performs it reliably at higher optimization levels, but you should not rely on it portably across all implementations for very deep recursion.

LISP's list structure (car/cdr) naturally supports recursive processing: handle the first element, recurse on the rest.
Every recursive function needs at least one base case to guarantee termination, typically (null lst) for lists or a numeric floor for counters.
A missing or incorrect reduction toward the base case causes infinite recursion and a stack-related error.
A recursive call is in tail position when it is the last operation performed, with no pending work after it returns.
Accumulator parameters convert non-tail-recursive functions into tail-recursive ones by carrying partial results forward.
Tail-call optimization reuses the current stack frame instead of growing the stack, but Common LISP does not guarantee it portably across implementations.
Recursive functions like sum-list and my-length demonstrate the base-case-plus-recursive-case pattern central to idiomatic LISP.