LISP递归

在 LISP以及 Scheme 等方言中递归Recursion拥有至高无上的地位。因为经典 LISP 提倡纯粹的函数式编程风格它没有专门的循环结构如for或while。在 LISP 里所有需要重复执行的逻辑全部都要通过函数自己调用自己——也就是递归来实现。理解 LISP 递归核心在于掌握它的两段式思维和现代 LISP 必须具备的尾递归优化。1. 递归的黄金法则两段式结构写 LISP 递归时脑子里必须时刻清醒地把代码拆成两部分基准条件Base Case / Terminal Case什么时候停下来通常是遇到空列表nil或数字到了0。递归步骤Recursive Step怎么把大问题拆成更小的问题通常是处理当前元素然后把剩下的部分丢给下一个递归。经典案例 1计算阶乘Factorialn!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(noptional(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 递归的优雅通过极其精简的代码自然地遍历了一棵复杂的非线性树结构。