Clojure尾递归与lazy-seq：详解lazy-seq如何保障尾递归安全

Great question! Let’s break this down clearly—because understanding lazy-seq is key to writing efficient, stack-safe recursive code in Clojure, especially when working with sequences.

First, let’s clarify what "unsafe" recursion means here. Normally, recursive functions (even tail-recursive ones, if not optimized) add a new frame to the call stack every time they invoke themselves. For large or infinite sequences, this stack will grow until it hits the JVM’s stack limit, causing a StackOverflowError.

Why Standard Tail Recursion Isn’t Always Enough #

Clojure does have tail call optimization via recur, but it only works if the recursive call is the very last thing the function does. For example:

(defn sum-to [n total]
  (if (zero? n)
    total
    (recur (dec n) (+ n total))))

This is stack-safe because recur replaces the current stack frame instead of adding a new one. But what if you want to return a sequence of values instead of a single result? You can’t use recur to build a sequence directly—trying to do something like (cons n (recur (inc n))) won’t work, because recur can’t be nested inside another expression.

How lazy-seq Solves This #

lazy-seq works by delaying the evaluation of the recursive call until it’s absolutely necessary. Here’s the core idea:

• When you wrap an expression in lazy-seq, it doesn’t run immediately. Instead, it returns a lightweight LazySeq object that knows how to compute the sequence’s elements later.
• When you access an element (e.g., with first, next, or by iterating), only that element is computed. The rest of the sequence remains a lazy promise.
• For recursive sequence generation, this means each recursive call is only triggered when the next element is requested. After computing one element, the stack frame is released before the next recursive call runs—so the stack never grows beyond a single frame, no matter how long the sequence is.

A Concrete Example: Infinite Natural Numbers #

Let’s look at a simple stack-safe infinite sequence using lazy-seq:

(defn natural-numbers [start]
  (lazy-seq
    (cons start (natural-numbers (inc start)))))

If you call (take 100000 (natural-numbers 1)), it won’t crash with a stack overflow. Here’s why:

• When you call natural-numbers 1, it returns a LazySeq without running the inner cons yet.
• When take asks for the first element, the cons runs: it returns 1 paired with another LazySeq (the result of (natural-numbers 2)).
• When take asks for the second element, it triggers the evaluation of (natural-numbers 2), which returns 2 paired with (natural-numbers 3)—and so on.
• Each time, the recursive call to natural-numbers only runs when the next element is needed, and the stack frame from the previous call is already gone. The stack depth never exceeds 1 for each element computation.

Another Example: Fibonacci Sequence #

A naive recursive Fibonacci function crashes quickly due to repeated calls and stack growth:

(defn fib-naive [n]
  (if (<= n 2)
    1
    (+ (fib-naive (- n 1)) (fib-naive (- n 2)))))

But a lazy-seq version is stack-safe and efficient:

(def fib-seq
  (lazy-seq
    (cons 1
          (lazy-seq
            (cons 1
                  (map + fib-seq (rest fib-seq)))))))

Here, fib-seq is an infinite lazy sequence. Even if you take the 100,000th element, it won’t stack overflow—because each step only computes the next element based on the previous ones, with no accumulated stack frames.

Key Takeaways #

• lazy-seq converts recursive sequence generation into piecemeal, on-demand computation. Instead of building the entire sequence at once (and overflowing the stack), it computes one element at a time.
• It avoids stack growth because each recursive call is deferred until the next element is needed, and the stack frame from the prior call is released before the next one runs.
• Unlike recur, it works for non-tail-recursive sequence patterns, making it far more flexible for generating sequences of any length (including infinite ones).

内容的提问来源于stack exchange，提问作者matanox