6.9 使用递归 (Using Recursion)

比起多数别的语言，递归在 Lisp 中扮演了一个重要的角色。这主要有三个原因：

1. 函数式程序设计。递归演算法有副作用的可能性较低。
2. 递归数据结构。 Lisp 隐式地使用了指标，使得递归地定义数据结构变简单了。最常见的是用在列表：一个列表的递归定义，列表为空表，或是一个 cons ，其中 cdr 也是个列表。
3. 优雅性。Lisp 程序员非常关心它们的程序是否美丽，而递归演算法通常比迭代演算法来得优雅。

学生们起初会觉得递归很难理解。但 3.9 节指出了，如果你想要知道是否正确，不需要去想递归函数所有的调用过程。

同样的如果你想写一个递归函数。如果你可以描述问题是怎么递归解决的，通常很容易将解法转成代码。要使用递归来解决一个问题，你需要做两件事：

1. 你必须要示范如何解决问题的一般情况，通过将问题切分成有限小并更小的子问题。
2. 你必须要示范如何通过 ── 有限的步骤，来解决最小的问题 ── 基本用例。

如果这两件事完成了，那问题就解决了。因为递归每次都将问题变得更小，而一个有限的问题终究会被解决的，而最小的问题仅需几个有限的步骤就能解决。

举例来说，下面这个找到一个正规列表（proper list）长度的递归算法，我们每次递归时，都可以找到更小列表的长度：

1. 在一般情况下，一个正规列表的长度是它的 cdr 加一。
2. 基本用例，空列表长度为 0 。

当这个描述翻译成代码时，先处理基本用例；但公式化递归演算法时，我们通常从一般情况下手。

前述的演算法，明确地描述了一种找到正规列表长度的方法。当你定义一个递归函数时，你必须要确定你在分解问题时，问题实际上越变越小。取得一个正规列表的 cdr 会给出 length 更小的子问题，但取得环状列表（circular list）的 cdr 不会。

这里有两个递归算法的示例。假定参数是有限的。注意第二个示例，我们每次递归时，将问题分成两个更小的问题：

第一个例子， member 函数，我们说某物是列表的成员，需满足：如果它是第一个元素的成员或是 member 的 cdr 的成员。但空列表没有任何成员。

第二个例子， copy-tree 一个 cons 的 copy-tree ，是一个由 cons 的 car 的 copy-tree 与 cdr 的 copy-tree 所组成的。一个原子的 copy-tree 是它自己。

一旦你可以这样描述算法，要写出递归函数只差一步之遥。

某些算法通常是这样表达最自然，而某些算法不是。你可能需要翻回前面，试试不使用递归来定义 our-copy-tree (41 页，译注: 3.8 小节)。另一方面来说，23 页 (译注: 2.13 节) 迭代版本的 show-squares 可能更容易比 24 页的递归版本要容易理解。某些时候是很难看出哪个形式比较自然，直到你试着去写出程序来。

如果你关心效率，有两个你需要考虑的议题。第一，尾递归（tail-recursive），会在 13.2 节讨论。一个好的编译器，使用循环或是尾递归的速度，应该是没有或是区别很小的。然而如果你需要使函数变成尾递归的形式时，或许直接用迭代会更好。

另一个需要铭记在心的议题是，最显而易见的递归算法，不一定是最有效的。经典的例子是费氏函数。它是这样递归地被定义的，

1. Fib(0) = Fib(1) = 1
2. Fib(n) = Fib(n-1)+Fib(n-2)

直接翻译这个定义，

(defun fib (n)
  (if (<= n 1)
      1
      (+ (fib (- n 1))
         (fib (- n 2)))))

这样是效率极差的。一次又一次的重复计算。如果你要找 (fib 10) ，这个函数计算 (fib 9) 与 (fib 8) 。但要计算出 (fib 9) ，它需要再次计算 (fib 8) ，等等。

下面是一个算出同样结果的迭代版本:

(defun fib (n)
  (do ((i n (- i 1))
       (f1 1 (+ f1 f2))
       (f2 1 f1))
      ((<= i 1) f1)))

迭代的版本不如递归版本来得直观，但是效率远远高出许多。这样的事情在实践中常发生吗？非常少 ── 这也是为什么所有的教科书都使用一样的例子 ── 但这是需要注意的事。