LISP - 递归

Lisp - 递归与尾调用优化

递归是函数式编程中的一个基本概念，也是在 Lisp 中表达许多算法的自然方式。它涉及函数通过将问题分解为更小、相似的子问题来调用自身以解决问题。本章不仅涵盖了基本递归，还包括了编写高效递归代码的关键概念：尾调用优化（TCO）。

递归函数的构成

每个正确的递归函数都包含两个关键组成部分：

• 基本情况：一个停止递归的条件。它是问题的最简单版本，无需进一步的递归调用即可直接解决。
• 递归步骤：函数调用自身的部分。关键在于，每次递归调用都必须朝着基本情况推进（例如，通过处理更小的数字或更短的列表）。

示例 1：一个简单（但有缺陷）的阶乘函数

让我们从经典的阶乘示例开始。这个实现易于理解，但存在显著的性能缺陷。

main.lisp（非尾递归）

;; 一个简单但非尾递归的阶乘函数。
(defun factorial (n)
  (if (<= n 1)
      1                               ; 基本情况
      (* n (factorial (- n 1)))))      ; 递归步骤

(print (factorial 5))

解释

该函数对于小数字能正确工作。但是，请注意递归步骤：(* n ...) 必须等待 (factorial (- n 1)) 的结果才能执行乘法。这意味着程序必须记住所有待处理的乘法，这会消耗调用栈上的内存。对于较大的 n，这将导致栈溢出。

尾调用优化（TCO）

尾调用是指在另一个函数中作为绝对最后一步的函数调用。一个优秀的 Lisp 编译器可以优化此类调用，使其不消耗栈空间，从而有效地将递归转化为高效的循环。这就是 TCO。

示例 2：一个尾递归的阶乘函数

为了使我们的阶乘函数实现尾递归，我们引入一个累加器参数来保存中间结果。这通常通过在主函数内部使用一个辅助函数来完成。

main.lisp（尾递归）

;; 一个高效的尾递归阶乘函数。
(defun factorial (n)
  (labels ((fact-iter (n accumulator))
             (if (<= n 1)
                 accumulator                           ; 基本情况：返回最终结果
                 (fact-iter (- n 1) (* n accumulator))))) ; 尾调用：没有待处理的操作
    (fact-iter n 1))) ; 对辅助函数的初始调用

;; 现在可以计算更大的阶乘而不会栈溢出。
(print (factorial 5))
(print (factorial 50)) ; 这在之前的版本中可能会失败

输出

120
30414093201713378043612608166064768844377641568960512000000000000

递归 vs. 迭代

尽管递归很优雅，但 Common Lisp 也拥有强大的迭代构造，如 loop、dotimes 和 dolist。那么何时使用哪种呢？

• 使用递归：当问题本身具有递归性质时，例如遍历树状数据结构。尾递归解决方案通常与迭代解决方案一样高效。
• 使用迭代：对于简单的线性循环（例如遍历列表或数字范围），loop 或 dotimes 通常更直接，也更容易让其他开发者阅读。

使用 loop 宏的阶乘函数

(defun factorial-loop (n)
  (loop for i from 1 to n
        for result = 1 then (* result i)
        finally (return result)))

(print (factorial-loop 5))

选择正确的工具——无论是优雅的递归还是强大的迭代——是成为一名精通 Lisp 程序员的关键技能。