LISP递归

在 LISP（以及 Scheme 等方言）中，递归（Recursion）拥有至高无上的地位。

因为经典 LISP 提倡纯粹的函数式编程风格，它没有专门的循环结构（如for或while）。在 LISP 里，所有需要重复执行的逻辑，全部都要通过函数自己调用自己——也就是递归来实现。

理解 LISP 递归，核心在于掌握它的两段式思维和现代 LISP 必须具备的尾递归优化。

1. 递归的黄金法则：两段式结构

写 LISP 递归时，脑子里必须时刻清醒地把代码拆成两部分：

1. 基准条件（Base Case / Terminal Case）：什么时候停下来？（通常是遇到空列表nil或数字到了0）。
2. 递归步骤（Recursive Step）：怎么把大问题拆成更小的问题？（通常是处理当前元素，然后把剩下的部分丢给下一个递归）。

经典案例 1：计算阶乘（Factorial）

n!=n×(n−1)×(n−2)×⋯×1n! = n \times (n-1) \times (n-2) \times \dots \times 1n!=n×(n−1)×(n−2)×⋯×1

用 Common LISP 编写如下：

(defunfactorial(n)(if(<=n1)1; 基准条件：n <= 1 时返回 1(*n(factorial(-n1))))); 递归步骤：n * (n-1) 的阶乘

经典案例 2：求列表长度（My-Length）

处理列表（List）是 LISP 的拿手好戏。LISP 内部的数据结构是链表，天然适合用car（获取第一个元素）和cdr（获取剩下所有元素组成的列表）来进行递归。

(defunmy-length(lst)(if(nulllst)0; 基准条件：空列表长度为 0(+1(my-length(cdrlst))))); 递归步骤：1 + 剩下列表的长度

2. 深度剖析：普通递归 vs 尾递归

上面写的两个标准递归虽然直观，但在处理大规模数据时有一个致命弱点：爆栈（Stack Overflow）。

普通递归的隐患

看回factorial的这行代码：(* n (factorial (- n 1)))。
当程序调用(factorial (- n 1))时，它不能释放当前函数的执行栈，因为云端还有个乘法(* n ...)在等着这个调用结果。

如果要计算(factorial 10000)，计算机会在内存里堆叠 10000 个等待返回的函数栈帧（Stack Frame），内存瞬间就被吃光了。

救星：尾递归（Tail Recursion）

如果一个函数在递归调用自己之后，不做任何其他的运算（比如乘法、加法），直接把这个调用结果作为自己的结果返回，这就叫尾递归。

由于后面没事干了，编译器或解释器可以非常聪明地复用当前的栈帧，直接把递归优化成和while循环一模一样的底层机器码，这就叫尾递归优化（Tail Call Optimization, TCO）。

怎么把普通递归改写为尾递归？

秘诀在于：引入一个“累加器”（Accumulator），让它在传递参数的过程中顺便把中间结果算好。

我们来改写阶乘：

(defuntail-factorial(n&optional(acc1))(if(<=n1)acc; 最终结果已经存在 acc 里了，直接返回(tail-factorial(-n1)(*n acc)))); 尾递归：调用完自己就结束了，没有任何后续运算

执行轨迹对比（以 3 的阶乘为例）：

• 普通递归：(factorial 3)→\rightarrow→(* 3 (factorial 2))→\rightarrow→(* 3 (* 2 (factorial 1)))→\rightarrow→逐层返回算出来。
• 尾递归：(tail-factorial 3 1)→\rightarrow→(tail-factorial 2 3)→\rightarrow→(tail-factorial 1 6)→\rightarrow→撞到基准条件，直接把6扔出来，期间只占用一个栈的空间。

3. LISP 递归的经典范式：CAR/CDR 递归

在 LISP 中，最常用的递归模式是同时对car（元素本身）和cdr（剩余列表）进行深度搜索。这常用于处理嵌套列表（树状结构）。

例如，写一个函数count-atoms，统计一个嵌套列表里一共有多少个非空原子元素（不管它嵌套得有多深，比如'(a (b c) d)里有 4 个原子）：

(defuncount-atoms(lst)(cond((nulllst)0); 情况 1：空列表，返回 0((atomlst)1); 情况 2：本身是个原子，返回 1(t(+(count-atoms(carlst)); 情况 3：是列表，递归左边(car)(count-atoms(cdrlst)))))); 加上递归右边(cdr)

这个小函数完美展现了 LISP 递归的优雅：通过极其精简的代码，自然地遍历了一棵复杂的非线性树结构。