11.3.3 基于列表的递归

之前那个打印数字列表元素的 while 循环示例 也可以用递归实现。下面是代码, 包含将变量 animals 设为列表的表达式。

如果你在 Emacs 的 Info 中阅读本文, 可以直接在 Info 中执行这些表达式。 否则必须把示例复制到 *scratch* 缓冲区再逐一执行。 使用 C-u C-x C-e 执行 (print-elements-recursively animals), 让结果打印在缓冲区中; 否则 Lisp 解释器会试图把结果挤在回显区的一行里。

另外,把光标放在 print-elements-recursively 函数最后一个右括号后面、注释前面的位置。 否则 Lisp 解释器会试图执行注释。

(setq animals '(gazelle giraffe lion tiger))

(defun print-elements-recursively (list)
  "Print each element of LIST on a line of its own.
Uses recursion."
  (when list                            ; do-again-test
        (print (car list))              ; body
        (print-elements-recursively     ; recursive call
         (cdr list))))                  ; next-step-expression

(print-elements-recursively animals)

print-elements-recursively 函数首先判断列表是否有内容; 如果有,函数打印列表的第一个元素,即列表的 CAR。 然后函数调用自身, 但参数不是整个列表,而是列表的第二个及后续元素,即列表的 CDR

换句话说,如果列表非空, 函数会启动另一段与初始代码相似的执行逻辑, 但属于不同的执行线程,参数也与第一个实例不同。

再换一种说法:如果列表非空, 第一个机器人会组装第二个机器人并指派任务; 第二个机器人与第一个个体不同,但型号相同。

第二次执行时,when 表达式被求值, 如果为真,就打印它收到的列表的第一个元素 (也就是原列表的第二个元素)。 然后函数用当前列表的 CDR 调用自身, 第二次时就是原列表 CDRCDR

注意,虽然我们说函数“调用自身(calls itself)”, 实际意思是 Lisp 解释器创建并指挥一个新的程序实例。 新实例是第一个的克隆体,但属于独立个体。

函数每次调用自身时, 都作用在原列表更短的一个版本上。 它创建一个新实例,处理更短的列表。

最终,函数会在空列表上调用自身。 它创建一个参数为 nil 的新实例。 条件表达式判断 list 的值。 由于 list 的值为 nilwhen 表达式返回假,因此 then 部分不执行。 函数整体返回 nil

*scratch* 缓冲区执行表达式 (print-elements-recursively animals) 后, 你会看到如下结果:

gazelle

giraffe

lion

tiger
nil