LISP - Recursion

Lisp - Recursion and Tail Call Optimization

Recursion is a fundamental concept in functional programming and a natural way to express many algorithms in Lisp. It involves a function calling itself to solve a problem by breaking it down into smaller, similar sub-problems. This chapter covers not only basic recursion but also the crucial concept of Tail Call Optimization (TCO) for writing efficient recursive code.

The Anatomy of a Recursive Function

Every correct recursive function has two key components:

• Base Case: A condition that stops the recursion. It’s the simplest version of the problem, which can be solved directly without further recursive calls.
• Recursive Step: The part of the function that calls itself. Crucially, each recursive call must progress towards the base case (e.g., by operating on a smaller number or a shorter list).

Example 1: A Simple (but flawed) Factorial

Let’s start with the classic factorial example. This implementation is easy to understand, but has a significant performance drawback.

main.lisp (Non-Tail-Recursive)

;; A simple, but not tail-recursive, factorial function.
(defun factorial (n)
  (if (<= n 1)
      1                               ; Base Case
      (* n (factorial (- n 1)))))      ; Recursive Step

(print (factorial 5))

Explanation

The function works correctly for small numbers. However, notice the recursive step: (* n ...) must wait for the result of (factorial (- n 1)) before it can perform the multiplication. This means the program has to remember all the pending multiplications, which consumes memory on the call stack. For a large n, this will lead to a stack overflow.

Tail Call Optimization (TCO)

A tail call is a function call that is the absolute last action in another function. A good Lisp compiler can optimize such calls so they don’t consume stack space, effectively turning recursion into a highly efficient loop. This is TCO.

Example 2: A Tail-Recursive Factorial

To make our factorial function tail-recursive, we introduce an accumulator argument to hold the intermediate result. This is often done using a helper function inside the main function.

main.lisp (Tail-Recursive)

;; An efficient, tail-recursive factorial function.
(defun factorial (n)
  (labels ((fact-iter (n accumulator))
             (if (<= n 1)
                 accumulator                           ; Base Case: return the final result
                 (fact-iter (- n 1) (* n accumulator))))) ; Tail Call: No pending operations
    (fact-iter n 1))) ; Initial call to the helper

;; This can now compute much larger factorials without stack overflow.
(print (factorial 5))
(print (factorial 50)) ; This would likely fail in the previous version

Output

120
30414093201713378043612608166064768844377641568960512000000000000

Recursion vs. Iteration

While recursion is elegant, Common Lisp also has powerful iteration constructs like loop, dotimes, and dolist. When should you use which?

• Use Recursion: When the problem is naturally recursive, such as traversing tree-like data structures. Tail-recursive solutions are often as efficient as iterative ones.
• Use Iteration: For simple, linear loops (like iterating over a list or a range of numbers), loop or dotimes can often be more direct and easier to read for other developers.

Factorial with the loop macro

(defun factorial-loop (n)
  (loop for i from 1 to n
        for result = 1 then (* result i)
        finally (return result)))

(print (factorial-loop 5))

Choosing the right tool—be it elegant recursion or powerful iteration—is a key skill in becoming a proficient Lisp programmer.