House in Common-lisp: Complete Solution & Deep Dive Guide

a close up of a computer screen with code on it

Mastering Recursion in Common Lisp: The Ultimate Guide to the House That Jack Built Problem

Learn to solve the 'House That Jack Built' problem in Common Lisp by mastering recursion and list processing. This guide explains how to dynamically construct the nursery rhyme's verses using recursive functions, string formatting, and functional programming techniques for elegant, efficient code.

You’ve stared at the function definition, tracing its logic in your head. It calls itself. Then it calls itself again. Suddenly, you’re lost in a mental labyrinth, a hall of mirrors where every reflection is the same function call. If this sounds familiar, you've encountered recursion, one of the most powerful yet initially bewildering concepts in programming. It feels abstract, almost magical, and notoriously difficult to debug.

But what if you could visualize this abstract process using a simple, memorable nursery rhyme? The cumulative tale of "This is the House That Jack Built" is a perfect real-world analogy for recursion. Each new verse builds upon the last, creating a chain of logic that mirrors a recursive function stack. In this deep-dive guide, we will demystify recursion entirely, using the unique strengths of Common Lisp to build an elegant solution from the ground up. You'll not only solve the problem but gain a profound, intuitive understanding of recursion that will elevate your programming skills.

What is the "House That Jack Built" Problem?

At its core, the problem asks us to programmatically generate the verses of the classic nursery rhyme, "This is the House That Jack Built." This isn't just a simple string generation task; the rhyme's structure is inherently cumulative and recursive. Each verse incorporates all the preceding verses.

Let's examine the structure:

Verse 1:

This is the house that Jack built.

Verse 2:

This is the malt
that lay in the house that Jack built.

Verse 3:

This is the rat
that ate the malt
that lay in the house that Jack built.

Notice the pattern. Verse 3 contains the core line of Verse 2, which in turn contains the entirety of Verse 1. This "embedding" of phrases is the key challenge. Our program must be able to construct any given verse, or a sequence of verses, by correctly layering these dependent clauses. This makes it a fantastic case study for list processing and recursive algorithms, two areas where Common Lisp truly shines.

The Core Challenge: Modeling Cumulative Logic

The primary difficulty isn't just printing text; it's managing the state and structure of this growing narrative. We need a way to represent the individual pieces of the rhyme—the subjects ("the rat", "the cat") and their actions ("that ate", "that killed")—and a mechanism to assemble them in the correct, reversed chronological order for each verse.

This challenge forces us to think about problems in terms of a "base case" (the simplest verse) and a "recursive step" (how to build a more complex verse from a simpler one). Successfully solving this demonstrates a solid grasp of fundamental computer science principles. For more foundational concepts, we recommend exploring our complete Common Lisp guide.

Why Use Common Lisp for This Challenge?

While this problem can be solved in any language, Common Lisp offers a uniquely elegant and idiomatic toolset that makes the solution feel natural and intuitive. Lisp, one of the earliest high-level programming languages, was designed from the ground up for symbolic computation and list manipulation, the very operations at the heart of this problem.

Reason 1: Homoiconicity (Code is Data)

In Lisp, the code itself is written using the language's primary data structure: the list. This property, known as homoiconicity, makes it incredibly easy to manipulate and generate code programmatically. For our problem, we can store the rhyme's components in a simple list of lists and process it with the same functions we use for any other data.


;; The rhyme's structure can be represented directly as a Lisp list.
(defparameter *rhyme-parts*
  '(("the horse and the hound and the horn" "belonged to")
    ("the farmer sowing his corn" "kept")
    ("the rooster that crowed in the morn" "woke")
    ("the priest all shaven and shorn" "married")
    ("the man all tattered and torn" "kissed")
    ("the maiden all forlorn" "milked")
    ("the cow with the crumpled horn" "tossed")
    ("the dog" "worried")
    ("the cat" "killed")
    ("the rat" "ate")
    ("the malt" "lay in")))

Reason 2: Powerful List Processing Primitives

Common Lisp provides a rich library of functions for list manipulation. Functions like car (get the first element), cdr (get the rest of the list), cons (add an element to the front), and nth (get the nth element) make deconstructing and reassembling our rhyme data trivial. This avoids the clumsy manual indexing and looping required in many other languages.

Reason 3: Natural Fit for Recursion

Functional programming is a core paradigm in Lisp, and recursion is its primary tool for iteration and flow control. The language and its implementations are highly optimized for recursive calls. Many Lisp compilers support Tail Call Optimization (TCO), which can turn certain types of recursive functions into efficient loops under the hood, preventing stack overflow errors even with deep recursion.

Reason 4: The REPL-Driven Workflow

Developing in Common Lisp is often done interactively using a Read-Eval-Print Loop (REPL). This allows you to build your solution piece by piece, testing each function as you write it. You can define your data, write a small helper function to format one line, test it immediately, and then build upon it. This iterative and interactive process is perfect for tackling a layered problem like this one.

How to Construct the Solution: A Step-by-Step Implementation

We will build our solution from the ground up, starting with data representation and moving to the recursive logic that assembles the verses. This methodical approach is a key part of the problem-solving process taught in the kodikra.com learning path.

Step 1: Representing the Rhyme's Data

As shown before, the most Lisp-y way to store the rhyme's components is a list of lists. Each inner list will contain two strings: the subject and the action. We store it in reverse order of appearance in the full rhyme, which simplifies our recursive logic later.


(defpackage #:house
  (:use #:cl)
  (:export #:recite))

(in-package #:house)

(defparameter *rhyme-parts*
  '(("the horse and the hound and the horn" "belonged to")
    ("the farmer sowing his corn" "kept")
    ("the rooster that crowed in the morn" "woke")
    ("the priest all shaven and shorn" "married")
    ("the man all tattered and torn" "kissed")
    ("the maiden all forlorn" "milked")
    ("the cow with the crumpled horn" "tossed")
    ("the dog" "worried")
    ("the cat" "killed")
    ("the rat" "ate")
    ("the malt" "lay in"))
  "A list of subject-verb pairs for the rhyme, in reverse order.")

(defparameter *base-line* "the house that Jack built."
  "The foundational line of every verse.")

We use defparameter to define two global variables: one for the rhyme's components and one for the unchanging base line. Storing the parts in reverse chronological order is a strategic choice. It means that to build the 3rd verse (about "the rat"), we only need to process the last 3 items of our list.

Step 2: The Recursive Core - Building a Single Verse

The heart of our solution will be a recursive helper function. This function's job is to take a subset of the *rhyme-parts* list and build the corresponding lines. Let's call it build-lines.

The logic follows a simple pattern:

Base Case: If the list of parts is empty, we're done. We just return the final line: "the house that Jack built."
Recursive Step: If the list is not empty, we take the first part (e.g., `("the rat" "ate")`), format it into a line like "that ate the rat", and then recursively call the function on the rest of the list. We then prepend our new line to the result of the recursive call.

Here is an ASCII diagram illustrating this recursive flow for building Verse 3.

    ● Start build-lines with '(("rat" "ate") ("malt" "lay in"))
    │
    ├─ Take first part: ("rat" "ate")
    │  Format line: "that ate the rat"
    │
    ▼ Call build-lines with '(("malt" "lay in"))
    │ │
    │ ├─ Take first part: ("malt" "lay in")
    │ │  Format line: "that lay in the malt"
    │ │
    │ ▼ Call build-lines with '() (empty list)
    │ │ │
    │ │ ├─ Base Case Reached!
    │ │ │
    │ │ └─ Return "the house that Jack built."
    │ │
    │ ├─ Receive result from inner call.
    │ │  Prepend "that lay in the malt"
    │ │
    │ └─ Return "that lay in the malt\nthat lay in the house that Jack built."
    │
    ├─ Receive result from middle call.
    │  Prepend "that ate the rat"
    │
    ▼ Final Result
    ┌──────────────────────────────────────────┐
    │ "that ate the rat\nthat lay in the malt\n" │
    │ "the house that Jack built."               │
    └──────────────────────────────────────────┘

This "unwinding" process, where the final result is assembled as the function calls return, is a classic example of recursion.

Step 3: Implementing the Common Lisp Code

Now let's translate this logic into actual Common Lisp code. We'll create a helper function verse-lines and a main function verse.


(defun verse-lines (parts)
  "Recursively builds the lines for a verse from a list of parts."
  (if (null parts)
      (list *base-line*)
      (let* ((part (first parts))
             (subject (first part))
             (verb (second part))
             (current-line (format nil "that ~a ~a" verb subject)))
        (cons current-line (verse-lines (rest parts))))))

(defun verse (n)
  "Generates the full text of a single verse, given its number (1-based)."
  (let* ((num-parts (1- n))
         (relevant-parts (subseq *rhyme-parts* (- (length *rhyme-parts*) num-parts)))
         (lines (verse-lines relevant-parts)))
    (format nil "This is ~{~a~^~%~}" lines)))

(defun recite (start-verse end-verse)
  "Generates the rhyme from a starting verse to an ending verse."
  (format nil "~{~a~^~%~%~}"
          (loop for i from start-verse to end-verse
                collect (verse i))))

Step 4: Detailed Code Walkthrough

Let's dissect this implementation to understand every piece.

`verse-lines (parts)`

(if (null parts) ...): This is our base case. If the input list parts is empty (null), it means we've processed all the components for this verse. We return a list containing only the final line, *base-line*.
(let* ((part (first parts)) ...): If the list is not empty, we use let* to create local bindings. first (or car) gets the first element, which is a two-element list like ("the rat" "ate").
(subject (first part)) and (verb (second part)): We extract the subject and verb from the part.
(format nil "that ~a ~a" verb subject): This is the magic of Common Lisp's format function. The first argument nil tells format to return the result as a string instead of printing it. ~a is a directive that aesthetically prints its corresponding argument. This line constructs strings like "that ate the rat".
(cons current-line (verse-lines (rest parts))): This is the recursive step. rest (or cdr) gets the list containing all but the first element. We call verse-lines on this smaller list. The cons function then takes our current-line and prepends it to the list of lines returned by the recursive call. This is how the verse is built from the bottom up.

`verse (n)`

(let* ((num-parts (1- n)) ...): This function takes a verse number n. Verse 1 has 0 extra parts, verse 2 has 1, and so on. So, the number of parts we need from our main list is n - 1. 1- is a shorthand function for subtracting one.
(relevant-parts (subseq *rhyme-parts* ...)): We use subseq to extract the correct slice of our *rhyme-parts* list. Since we stored them in reverse, we calculate the starting index from the end of the list.
(lines (verse-lines relevant-parts)): We call our recursive helper to get the list of lines for this verse.
(format nil "This is ~{~a~^~%~}" lines): Another powerful format directive. ~{...~} iterates over a list (in this case, lines). Inside the loop, ~a prints each element, and ~^~% acts as a separator. It prints a newline (~%) between elements but not after the last one. This elegantly joins our list of lines into a single, correctly formatted string, prepended with "This is ".

`recite (start-verse end-verse)`

This is our main entry point. It uses a loop macro to iterate from the start-verse to the end-verse.
collect (verse i): For each number i in the range, it calls our verse function and collects the resulting string into a list.
(format nil "~{~a~^~%~%~}" ...): Finally, it uses the same iteration directive as before, but this time it joins the complete verses with a double newline (~%~%) to separate them, as required by the problem.

Alternative Approaches: Iteration vs. Recursion

While recursion provides a very elegant and readable solution for this problem, it's not the only way. An iterative approach using a loop is also perfectly valid and can be more memory-efficient for extremely large inputs (though that's not a concern here).

An Iterative Solution

An iterative version of verse-lines might look like this:


(defun verse-lines-iterative (parts)
  "Iteratively builds the lines for a verse."
  (let ((lines (list *base-line*)))
    (loop for part in (reverse parts) do
      (let* ((subject (first part))
             (verb (second part))
             (current-line (format nil "that ~a ~a" verb subject)))
        (push current-line lines)))
    lines))

In this version, we first reverse the list of parts so we can process them in the correct order. We initialize our lines list with the base line. Then, we loop through the parts, building each line and using push (which is equivalent to (setf lines (cons new-item lines)))) to add it to the front of our accumulator list. This builds the verse in the correct order without any recursive function calls.

Here is an ASCII diagram comparing the logical flow of both approaches.

    Recursive Approach                      Iterative Approach
    ──────────────────                      ──────────────────
    ● verse(3)                              ● verse-iterative(3)
    │                                       │
    ├─ Calls verse(2)                       ├─ Initialize lines = ["...house..."]
    │  │                                    │  Reverse parts -> (("malt"), ("rat"))
    │  ├─ Calls verse(1)                    │
    │  │  │                                 ▼ Loop 1: part = ("malt")
    │  │  ├─ Base Case returns ["...house..."] │  Create line: "that lay in the malt"
    │  │  │                                 │  Push to lines -> ["...malt...", "...house..."]
    │  │  ▼                                 │
    │  ├─ Prepends "...malt..."             ▼ Loop 2: part = ("rat")
    │  │  Returns ["...malt...", "...house..."] │  Create line: "that ate the rat"
    │  │                                    │  Push to lines -> ["...rat...", "...malt...", "...house..."]
    │  ▼                                    │
    ├─ Prepends "...rat..."                 ├─ Loop finishes
    │  Returns ["...rat...", "...malt...", "...house..."] │
    │                                       │
    ▼                                       ▼
    ● Final List Assembled                  ● Final List Assembled

Pros and Cons

Choosing between recursion and iteration often involves a trade-off. Here’s a comparison in the context of our problem:

Aspect	Recursive Approach	Iterative Approach
Readability	Often more closely matches the problem's definition. The code `(cons current-line (recursive-call ...))` directly mirrors the idea of "this line plus the rest of the verse."	Can be more straightforward for developers unfamiliar with recursion. The state is managed explicitly in a loop variable.
Performance	Each function call adds a frame to the call stack, which can incur a small overhead. For very deep recursion, this could lead to a stack overflow.	Generally faster and more memory-efficient as it avoids the overhead of function calls. No risk of stack overflow.
Idiomatic Lisp	Highly idiomatic. Recursion over lists is a fundamental pattern in all Lisp dialects.	Also idiomatic. The `loop` macro is extremely powerful and is a common tool for iteration in Common Lisp.
Complexity	The logic is self-contained. The base case and recursive step are clearly defined in one function.	May require extra steps like reversing the list beforehand to build the result in the correct order.

For this specific problem, the number of verses is small, so the performance difference is negligible. The recursive solution is arguably more elegant and a better demonstration of the core computer science concept at play.

Real-World Applications of This Pattern

The cumulative, recursive pattern demonstrated in this rhyme isn't just an academic exercise. It appears in many real-world computing scenarios.

File System Paths: A file path like /home/user/documents/report.txt is a nested structure. To resolve the path, you process "home", then "user" within "home", and so on. This is a recursive composition.
Parsing Nested Data Formats (JSON/XML): When you parse a JSON object, you often write a function that handles a value. If that value is itself an object or an array, the function calls itself on that inner structure.
Rendering UI Components: Modern UI frameworks like React build user interfaces from components that can contain other components. Rendering the main `App` component involves recursively rendering all its children until only basic HTML elements remain.
Dependency Resolution: In a build system or package manager, resolving the dependencies for a package `A` might require first resolving the dependencies for packages `B` and `C`, which `A` depends on. This forms a recursive dependency graph.

Understanding this pattern through a simple example like the "House That Jack Built" provides a solid mental model for tackling these more complex, practical problems.

Frequently Asked Questions (FAQ)

What is tail-call optimization (TCO) and does it apply here?

Tail-call optimization is a compiler feature where a function call in the "tail position" (the very last thing the function does) is transformed into a simple jump, reusing the current stack frame. This prevents the call stack from growing. Our primary recursive function, verse-lines, is not tail-recursive because the last operation is cons, not the recursive call itself. A tail-recursive version would require an "accumulator" argument.

Why is the format function in Common Lisp so powerful?

Common Lisp's format is a mini-language for string formatting. Unlike simple C-style printf, it includes directives for iteration (~{...~}), conditionals (~[...]), pluralization, number formatting (binary, octal, hex, Roman numerals), and more. It allows for incredibly sophisticated text generation in a very concise way, as demonstrated in our solution.

Is recursion always slower than iteration?

Not necessarily. While there is function call overhead, modern compilers are very good at optimization. For problems that are naturally recursive, the recursive code can be clearer and less prone to bugs. For performance-critical code on very large datasets, an iterative solution is often preferred, but the difference is usually negligible for most tasks.

How does Lisp's cons function relate to building lists?

In Lisp, a list is fundamentally a linked series of "cons cells." A cons cell is a pair containing two pointers: the car (the value) and the cdr (a pointer to the next cell or nil). The cons function creates a new cell, making its first argument the car and its second argument the cdr. By repeatedly "consing" an element onto an existing list, you build a new, longer list without modifying the original—a key concept in functional programming.

What is the difference between car/cdr and first/rest?

Functionally, they are often the same. first is an alias for car, and rest is an alias for cdr. The names first and rest were introduced to be more intuitive for newcomers. The original names car (Contents of the Address Register) and cdr (Contents of the Decrement Register) are historical artifacts from the IBM 704 computer on which Lisp was first implemented.

Could I use a different data structure, like a hash table?

You could, but it would be less natural for this problem. A hash table would be useful if you needed to look up a verse component by a key, but the problem requires processing a specific, ordered sequence. A list is the ideal data structure for representing an ordered sequence, making it the superior choice here.

Why start the rhyme from the end of the data list?

We stored the rhyme parts in reverse chronological order and used subseq to grab a slice from the end of the list. This makes the logic simpler. For verse `n`, we need the last `n-1` elements. This is an easy slice to calculate. If we stored them in chronological order, we'd still need to select the first `n-1` elements and then recursively process them in reverse, which would add a bit of complexity.

Conclusion: From Nursery Rhymes to Elegant Code

We've journeyed from a simple nursery rhyme to a deep exploration of recursion, list processing, and idiomatic Common Lisp. The "House That Jack Built" problem, while seemingly trivial, serves as a powerful vehicle for understanding how to break down a problem into a base case and a recursive step. By representing the rhyme's structure as a list—Lisp's native tongue—we were able to craft a solution that is not only functional but also remarkably elegant and expressive.

The key takeaway is that recursion is a tool for thinking. It allows you to define a problem in terms of itself, simplifying complex, nested logic into a few lines of code. Mastering this concept unlocks solutions to a vast array of problems, from parsing data to building complex systems. As you continue your journey through the kodikra.com Common Lisp modules, you will find this recursive pattern appearing time and time again, and now you have the solid foundation needed to tackle it with confidence.

Disclaimer: The code in this article is written for modern Common Lisp implementations (like SBCL 2.4+). While the core functions are standard, behavior may vary slightly between different implementations.

Published by Kodikra — Your trusted Common-lisp learning resource.

kodikra

Search this blog