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 调用自身, 第二次时就是原列表 CDR 的 CDR。

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

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

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

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

gazelle

giraffe

lion

tiger
nil