2.7 递归 (Recursion)

上一节我们所定义的函数，调用了别的函数来帮它们做事。比如 sum-greater 调用了 + 和 > 。函数可以调用任何函数，包括自己。自己调用自己的函数是递归的。 Common Lisp 函数 member ，测试某个东西是否为列表的成员。下面是定义成递归函数的简化版：

  1. > (defun our-member (obj lst)
  2.    (if (null lst)
  3.        nil
  4.    (if (eql (car lst) obj)
  5.        lst
  6.        (our-member obj (cdr lst)))))
  7. OUR-MEMBER

谓词 eql 测试它的两个实参是否相等；此外，这个定义的所有东西我们之前都学过了。下面是运行的情形：

  1. > (our-member 'b '(a b c))
  2. (B C)
  3. > (our-member 'z '(a b c))
  4. NIL

下面是 our-member 的定义对应到英语的描述。为了知道一个对象 obj 是否为列表 lst 的成员，我们

  1. 首先检查 lst 列表是否为空列表。如果是空列表，那 obj 一定不是它的成员，结束。
  2. 否则，若 obj 是列表的第一个元素时，则它是列表的成员。
  3. 不然只有当 obj 是列表其余部分的元素时，它才是列表的成员。

当你想要了解递归函数是怎么工作时，把它翻成这样的叙述有助于你理解。

起初，许多人觉得递归函数很难理解。大部分的理解难处，来自于对函数使用了错误的比喻。人们倾向于把函数理解为某种机器。原物料像实参一样抵达；某些工作委派给其它函数；最后组装起来的成品，被作为返回值运送出去。如果我们用这种比喻来理解函数，那递归就自相矛盾了。机器怎可以把工作委派给自己？它已经在忙碌中了。

较好的比喻是，把函数想成一个处理的过程。在过程里，递归是在自然不过的事情了。日常生活中我们经常看到递归的过程。举例来说，假设一个历史学家，对欧洲历史上的人口变化感兴趣。研究文献的过程很可能是：

  1. 取得一个文献的复本
  2. 寻找关于人口变化的资讯
  3. 如果这份文献提到其它可能有用的文献，研究它们。

过程是很容易理解的，而且它是递归的，因为第三个步骤可能带出一个或多个同样的过程。

所以，别把 our-member 想成是一种测试某个东西是否为列表成员的机器。而是把它想成是，决定某个东西是否为列表成员的规则。如果我们从这个角度来考虑函数，那么递归的矛盾就不复存在了。