递归在Clojure里特别常见，但很多人一写递归就担心把栈搞爆。这个担心不是多余的：如果你用别的语言写习惯了循环，到了Clojure突然发现没有for没有while，只能靠递归，那确实得把递归的脾气摸清楚。今天咱们就从一个普通开发者的角度，聊一聊Clojure递归优化的实战方法，以及那些容易踩进去的坑。

一、先说说递归和栈的关系

1.1 递归为什么会爆栈

递归就是函数调用自己。每次调用一次函数，JVM就要为这次调用分配一块栈帧，用来存局部变量、参数、返回地址这些东西。正常情况下，函数调用完，栈帧就释放了。但递归不是，它一层层往下调，每一层都还没结束，新的调用又进来了，栈帧只能越叠越高。当高度超过JVM允许的栈深度时，就报StackOverflowError。

比如你写一个求1到n之和的函数：

;; 非尾递归的求和：先递归求 sum(- n 1)，再把 n 加上去
(defn sum-to-n [n]
  (if (<= n 0)
    0
    (+ n (sum-to-n (dec n)))))

在REPL里直接跑一下：

(sum-to-n 100000)

大概率会抛出一大堆StackOverflowError。原因很简单：函数最后一件事是做什么？它是先递归调用(sum-to-n (dec n))，等这个调用返回一个数字，再拿这个数字和n相加。也就是说，每次调用都不能立刻返回，必须等着下一层的结果，栈自然越叠越深。

1.2 为什么循环不会爆栈

循环没有栈帧堆积，因为它是同一帧里跳来跳去。所以Clojure希望我们用一种“看起来像递归，其实本质是循环”的方式来写代码。这就轮到loop/recur出场了。

二、尾递归和recur

2.1 什么是尾调用

一个函数如果最后一步是调用另一个函数，并且调用的结果直接作为当前函数返回值，那这就是尾调用。尾调用不用等谁，所以理论上可以把当前函数的栈帧直接复用来跑新函数。Clojure里的recur就是专门干这个的，它允许你跳回到当前函数的开头，并且换一批参数重新执行，整个过程不新增栈帧。

2.2 用loop/recur改写求和

把上面的sum-to-n改成尾递归，最简单的方式是额外带一个累加参数：

;; 使用 loop 和 recur 实现累加
;; cur 是当前还剩多少要加
;; acc 是已经累加的结果
(defn sum-to-n-tail [n]
  (loop [cur n
         acc 0]
    (if (<= cur 0)
      acc
      ;; 直接告诉程序：下一轮循环用这两个新值
      (recur (dec cur) (+ acc cur)))))

这里loop定义了循环的起点，初始cur为n，acc为0。每次recur都相当于把控制权交回给loop，用新的参数重新执行。没有递归调用等待，也没有栈帧堆积。即便n是几百万，只要JVM内存够，它也能平稳跑完。

你可以用time简单感受一下：

(time (sum-to-n-tail 1000000))

输出大概是“Elapsed time: ... ms”，然后给你一个很大的数字。

2.3 把非尾递归改成尾递归

再看一个更复杂点的例子：斐波那契。教科书写法是：

;; 朴素的斐波那契，双重递归，又慢又容易爆栈
(defn fib [n]
  (if (< n 2)
    n
    (+ (fib (dec n)) (fib (- n 2)))))

这个版本每个n得算两棵树，指数级增长，n稍微大一点就卡死了。尾递归版本要转换思路，用两个变量保存前两个值：

;; 尾递归版斐波那契
;; a 保存 fib(n) 的值
;; b 保存 fib(n+1) 的值
;; i 是计数器，从 n 减到 0
(defn fib-tail [n]
  (loop [a 0
         b 1
         i n]
    (if (zero? i)
      a
      (recur b (+ a b) (dec i)))))

跑(fib-tail 1000)也会很快结束。注意，recur必须出现在函数体的尾部，如果你这么写：

(defn bad-fib [n]
  (if (> n 0)
    (+ n (recur (dec n))) ; 编译器会直接报错
    0))

Clojure会告诉你recur不在尾部位置，编译不通过。这也是很多新手最初搞不明白的地方：recur不是在哪儿都能用，它只能出现在“当前循环的最后一步”。

三、惰性序列也是一种递归优化

3.1 用lazy-seq生成无限序列

有些问题不适合用计数器，比如要表示自然数序列、无限流、树的孩子节点等等。这时候lazy-seq就特别有用，它能把计算推迟到真正需要值的时候。

举个例子，生成从某个整数开始的无限自然数：

;; 返回一个惰性序列，从 start 开始一个一个往上加
(defn naturals [start]
  (lazy-seq
    (cons start (naturals (inc start)))))

你不用担心(naturals 0)死循环，因为它外层包了lazy-seq，递归调用不会立刻发生。只有当你使用take、first这类操作去要数据时，它才会生成必要的那几个元素：

(take 5 (naturals 0))
;; 输出: (0 1 2 3 4)

3.2 关联技术：iterate

其实这种“从初始值不断应用某个函数”的序列，Clojure早就替你封装好了，就是iterate：

;; iterate 用法：(iterate f seed)
;; 返回 seed, (f seed), (f (f seed)) ...
(def naturals-2 (iterate inc 0))

;; 取前5个
(take 5 naturals-2)

iterate内部也是基于惰性递归实现的，它的好处是代码更短，人也更不容易写错。但你必须明白，惰性不是“没有计算”，而是“按需计算”。按需计算也带来了一些麻烦。

3.3 惰性序列的坑

第一个坑：惰性序列会缓存已经计算出的值。如果你把一个很大的惰性序列存下来，并一直持有它的头部，那么它已经算过的那部分会被留在内存里。比如：

;; 定义一个巨大的惰性序列
(def h (map identity (range 1000000)))

;; count 会要求把所有元素都实现出来
(count h)

;; 此时 h 已经缓存了所有元素，内存占用相当可观

如果你只是想算一个总和，就不应该持有这个序列，而是应该用reduce一次过：

(reduce + 0 (map identity (range 1000000)))

这样遍历完，中间结果不会被长期保留。

第二个坑和“块状”有关。Clojure的map、range默认是分块惰性的，也就是一次实现32个元素，而不是一个一个地来。当你写：

;; 注意：这条命令会打印很多数字，不只是5个
(take 5 (map #(do (print % " ")) (range)))

打印结果可能是0 1 2 3 4 5 6 ... 31这样的32个数字，然后才返回前5个元素。因为底层为了获取前5个，已经一次性生成了32个元素。如果你的计算有副作用，或者代价很高，这个行为会让你措手不及。这时候可以自己写一个非分块的惰性map，控制实现粒度：

;; 自定义惰性 map，保证每次只实现一个元素
(defn lazy-map-one [f coll]
  (when-let [s (seq coll)]
    (lazy-seq
      (cons (f (first s))
            (lazy-map-one f (rest s))))))

不过在大多数纯计算场景下，分块反而能提升性能，所以不用刻意避开，只要心里清楚有这回事就行。

四、互相递归和trampoline

4.1 什么是互相递归

有时候两个函数会互相调用。比如判断一个数是偶数还是奇数，可以用一个很幼稚但很清晰的写法：

;; 先声明两个函数名，允许后面互相引用
(declare my-even? my-odd?)

(defn my-even? [n]
  (if (= n 0)
    true
    (my-odd? (dec n))))

(defn my-odd? [n]
  (if (= n 0)
    false
    (my-even? (dec n))))

这个逻辑是对的，但它对栈的消耗非常明显。每次my-even?调my-odd?，再调my-even?，每一层都留在栈上，n稍微大一点就爆了。

4.2 用trampoline解决

Clojure提供了一个叫trampoline的函数，它的思路很聪明：让这些递归函数不直接调用对方，而是返回一个“还没执行的函数”，由trampoline在自家里循环调用。这样栈深度始终只有一层。

改写上面的判断函数：

(declare my-even2? my-odd2?)

(defn my-even2? [n]
  (if (= n 0)
    true
    ;; 注意这里返回的是闭包，而不是直接调用
    #(my-odd2? (dec n))))

(defn my-odd2? [n]
  (if (= n 0)
    false
    #(my-even2? (dec n))))

然后调用：

(trampoline my-even2? 100000)
;; 返回 true

只要n还够大，它都不会栈溢出。trampoline会不停地执行返回的函数，直到某个分支返回一个非函数的值，比如true或false。你可以把这种写法理解成：把递归调用变成了一个“函数链”，然后循环去解这条链。

4.3 和recur的对比

recur只能让一个函数跳回自己的开头，天生不支持两个函数互相递归。trampoline则是处理互相递归的标准工具。但它的代价是必须把函数返回值改造成“函数”或“最终结果”的形式，代码可读性会稍微差一点。所以只有明确遇到互相递归，或者你不想写loop/recur的时候，再考虑用它。

五、记忆化避免重复计算

递归还有一个很头疼的问题：重复计算。还是拿斐波那契说话，朴素递归里(fib 5)要算很多次(fib 2)，越往下重复越多。Clojure自带memoize，可以直接给函数加缓存：

;; 定义一个被缓存了结果的斐波那契函数
;; 这里不能写成 defn fib-memo，因为递归时需要引用 fib-memo 本身
(def fib-memo
  (memoize
    (fn [n]
      (if (< n 2)
        n
        (+ (fib-memo (- n 1))
           (fib-memo (- n 2)))))))

这样第一次计算某个n时会递归算出所有依赖项，并把结果缓存起来，之后再要同样参数就直接返回，不再重复算。但要注意，memoize没有解决“递归深度”问题。这个fib-memo本质上还是非尾递归，如果你传入一个特别大的n，比如100000，它仍然会栈溢出。它解决的是“指数级重复计算”这个性能问题，而不是“栈帧堆积”问题。

什么时候适合用记忆化？比如你在做树形动态规划、爬楼梯问题、背包问题，很多子问题会被反复用到，缓存一下收益巨大。但如果你需要非常深的递归，记忆化救不了你，还是得靠recur或循环。

六、实战中常见的坑点

6.1 别把recur当成万能药

recur确实很好用，但它只能在尾部调用，而且只能作用于当前函数或loop块。你没法用它来从一个函数跳转到另一个函数，也没法在它后面再接别的计算。遇到这种情况，要么用trampoline，要么用惰性序列，要么换个思路用高阶函数。

6.2 别为了尾递归而尾递归

有些问题天生适合用惰性序列来表达，比如无限流。如果非要改成尾递归，你会加一个计算步数参数，然后在循环里不断recur，写起来又丑又绕。反过来，对于纯累加、纯计数器这类场景，尾递归非常稳。所以要先想清楚数据形态，再选择优化手段。

6.3 忘记惰性序列会持有头部

前面已经提过，惰性序列会缓存已实现的值。如果你在递归函数里一个一个地rest，同时还把原始序列对象一直保存在变量里，那么所有已经“路过”的元素也都会被缓存，内存会越吃越多。一个典型错误写法：

;; 错误的示范：s 一直持有原序列头部，导致缓存无法释放
(defn walk-seq [s]
  (when-let [s (seq s)]
    (do (println (first s))
        (walk-seq (rest s)))))

表面看每次递归都只取rest，但原始s作为参数一直在调用栈里，遍历过的节点不会马上释放。更好的做法是用reduce、run!这类一次性消费的函数，让垃圾回收尽早处理掉没用的部分。

6.4 忽略了分块惰性的副作用

前面已经演示过take 5实际上可能算32个元素。如果你在map的函数里有打印日志、写数据库、调用远端接口这类操作，那么分块惰性会让这些额外操作莫名其妙地发生。最稳妥的规避方案就是少在惰性序列里放副作用，或者把副作用延迟到真正消费的时候。如果实在要精细控制，就自己写lazy-map-one，也就是前面那种逐元素实现的函数。

七、应用场景与优缺点

7.1 适合用递归的场景

递归适合处理“嵌套”结构，比如文件目录、树形菜单、XML/HTML节点、语法树。这类结构深度不确定，而且天然是递归定义的。处理的时候用递归函数逐层往下走，代码看起来最清楚。另外，闭包里的状态切换也常常用递归，比如状态机里的状态相互转换，用到互相递归时，trampoline就能派上用场。

7.2 几种优化方式怎么选

loop/recur适合累加、计数、单函数尾递归，性能最好，接近普通循环。
lazy-seq适合生成无限序列、流式数据、按需计算，能省掉不必要的计算，但要小心缓存和分块。
trampoline适合互相递归，能把深栈变成循环，代价是代码要写成返回函数的形式。
memoize适合有大量重复子问题的递归，能极大提升速度，但不会降低递归深度。

实际开发里，它们完全可以组合。比如用lazy-seq包一层，内部用loop/recur生成下一个元素；或者用memoize缓存中间结果，再用recur控制深度。没有银弹，只有合适不合适。

7.3 必须注意的几个点

第一，测试递归函数时，一定要测大输入，比如100000、1000000，别只测几个小数字就觉得自己写对了。第二，写递归前先看看Clojure标准库有没有现成的函数，比如map、filter、reduce、iterate，很多“递归”其实可以一句话搞定。第三，注意使用zero?判断是否为零，真是性更好读。第四，别在惰性序列里塞副作用，否则分块惰性会给你带来惊喜。第五，recur的位置只能在尾部，编译不过就换个写法。

八、总结

Clojure里做递归优化，不是靠某一个技巧，而是靠对几种工具的准确理解。recur解决单函数尾递归，lazy-seq解决无限和按需计算，trampoline解决互相递归，memoize解决重复子问题。真正的坑在于这些工具的使用边界：recur只能在尾位置，惰性序列会缓存并可能分块，记忆化救不了栈深度。把这些边界摸清楚，你就能写出既优雅又稳的Clojure递归代码。下次再遇到栈溢出，先别慌，看看是不是用错了工具。递归不是洪水猛兽，了解它，它就是你手里的好工具。