Recursively defined sequences are pretty but difficult to get right when you don’t want to assign the sequence to a var. Here is a couple of macros to ease recursive definitions.

(defmacro rec-cat 
 "Similar to lazy-cat but binds the resulting sequence using the supplied 
  binding-form, allowing recursive expressions. The first collection 
  expression must not be recursive and must return a non-nil seq."
 [binding-form expr & rec-exprs]
  `(let [rec-rest# (atom nil)
         result# (lazy-cat ~expr (force @rec-rest#))
         ~binding-form result#]
     (swap! rec-rest# (constantly (delay (lazy-cat ~@rec-exprs))))
     result#))
         
(defmacro rec-cons 
 "Similar to lazy-cons but binds the resulting sequence using the supplied 
  binding-form, allowing recursive expressions. The first expression must 
  not be recursive and must return a non-nil seq."
 [binding-form expr & rec-exprs]
  `(let [rec-rest# (atom nil)
         result# (lazy-cons ~expr (force @rec-rest#))
         ~binding-form result#]
     (swap! rec-rest# (constantly (delay (lazy-cat ~@rec-exprs))))
     result#))

Examples:

Natural numbers (just like (iterate inc 0)):

(rec-cons naturals 0 (map inc naturals))

fibonnaci sequence:

(rec-cat fibs [0 1] (map + fibs (rest fibs)))

Chouser’s cute reduction:

(defn reduction
  "Returns a lazy seq of the intermediate values of the reduction (as
  per reduce) of coll by f, starting with init."
  ([f coll]
   (if (seq coll)
     (rec-cons reductions (first coll) (map f reductions (rest coll)))
     (cons (f) nil)))
  ([f init coll]
   (rec-cons reductions init (map f reductions coll))))