命令式语言开发人员并不经常使用递归这一工具，因为他们认为这样会较慢而且浪费空间，不过，作者通过示例表明，可以使用一些技术来尽减少或者避免这些问题。他介绍了递归以及递归程序设计模式的概念，研究了如何使用它们来编写保证正确的程序。示例是使用 Scheme 和 C 编写的。

计算机科学的新学生通常难以理解递归程序设计的概念。递归思想之所以困难，原因在于它非常像是循环推理（circular reasoning）。它也不是一个直观的过程；当我们指挥别人做事的时候，我们极少会递归地指挥他们。

对刚开始接触计算机编程的人而言，这里有递归的一个简单定义：当函数直接或者间接调用自己时，则发生了递归。

递归的经典示例
计算阶乘是递归程序设计的一个经典示例。计算某个数的阶乘就是用那个数去乘包括 1 在内的所有比它小的数。例如，factorial(5) 等价于 5*4*3*2*1，而 factorial(3) 等价于 3*2*1。

阶乘的一个有趣特性是，某个数的阶乘等于起始数（starting number）乘以比它小一的数的阶乘。例如，factorial(5) 与 5 * factorial(4) 相同。您很可能会像这样编写阶乘函数：

            int factorial(int n)
            {
            return n * factorial(n - 1);
            }
            

不过，这个函数的问题是，它会永远运行下去，因为它没有终止的地方。函数会连续不断地调用 factorial。当计算到零时，没有条件来停止它，所以它会继续调用零和负数的阶乘。因此，我们的函数需要一个条件，告诉它何时停止。

由于小于 1 的数的阶乘没有任何意义，所以我们在计算到数字 1 的时候停止，并返回 1 的阶乘（即 1）。因此，真正的递归函数类似于：

            int factorial(int n)
            {
            if(n == 1)
            {
            return 1;
            }
            else
            {
            return n * factorial(n - 1);
            }
            }
            

可见，只要初始值大于零，这个函数就能够终止。停止的位置称为 基线条件（base case）。基线条件是递归程序的最底层位置，在此位置时没有必要再进行操作，可以直接返回一个结果。所有递归程序都必须至少拥有一个基线条件，而且必须确保它们最终会达到某个基线条件；否则，程序将永远运行下去，直到程序缺少内存或者栈空间。

递归程序的基本步骤
每一个递归程序都遵循相同的基本步骤：

1. 初始化算法。递归程序通常需要一个开始时使用的种子值（seed value）。要完成此任务，可以向函数传递参数，或者提供一个入口函数，这个函数是非递归的，但可以为递归计算设置种子值。
2. 检查要处理的当前值是否已经与基线条件相匹配。如果匹配，则进行处理并返回值。
3. 使用更小的或更简单的子问题（或多个子问题）来重新定义答案。
4. 对子问题运行算法。
5. 将结果合并入答案的表达式。
6. 返回结果。

使用归纳定义
有时候，编写递归程序时难以获得更简单的子问题。不过，使用 归纳定义的（inductively-defined）数据集 可以令子问题的获得更为简单。归纳定义的数据集是根据自身定义的数据结构 —— 这叫做 归纳定义（inductive definition）。

例如，链表就是根据其本身定义出来的。链表所包含的节点结构体由两部分构成：它所持有的数据，以及指向另一个节点结构体（或者是 NULL，结束链表）的指针。由于节点结构体内部包含有一个指向节点结构体的指针，所以称之为是归纳定义的。

使用归纳数据编写递归过程非常简单。注意，与我们的递归程序非常类似，链表的定义也包括一个基线条件 —— 在这里是 NULL 指针。由于 NULL 指针会结束一个链表，所以我们也可以使用 NULL 指针条件作为基于链表的很多递归程序的基线条件。

链表示例
让我们来看一些基于链表的递归函数示例。假定我们有一个数字列表，并且要将它们加起来。履行递归过程序列的每一个步骤，以确定它如何应用于我们的求和函数：

1. 初始化算法。这个算法的种子值是要处理的第一个节点，将它作为参数传递给函数。
2. 检查基线条件。程序需要检查确认当前节点是否为 NULL 列表。如果是，则返回零，因为一个空列表的所有成员的和为零。
3. 使用更简单的子问题重新定义答案。我们可以将答案定义为当前节点的内容加上列表中其余部分的和。为了确定列表其余部分的和，我们针对下一个节点来调用这个函数。
4. 合并结果。递归调用之后，我们将当前节点的值加到递归调用的结果上。

下面是这个函数的伪代码和实际代码：

            function sum_list(list l)
            is l null?
            yes - the sum of an empty list is 0 - return that
            data = head of list l
            rest_of_list = rest of list l
            the sum of the list is:
            data + sum_list(rest_of_list)
            

这个程序的伪代码几乎与其 Scheme 实现完全相同。

            (define sum-list (lambda (l)
            (if (null? l)
            0
            (let (
            (data (car l))
            (rest-of-list (cdr l)))
            (+ data (sum-list rest-of-list))))))
            

对于这个简单的示例而言，C 版本同样简单。

            int sum_list(struct list_node *l)
            {
            if(l == NULL)
            return 0;
            return l.data + sum_list(l.next);
            }
            

您可能会认为自己知道如何不使用递归编写这个程序，使其执行更快或者更好。稍后我们会讨论递归的速度和空间问题。在此，我们继续讨论归纳数据集的递归。

假定我们拥有一个字符串列表，并且想要知道某个特定的字符串是否包含在那个列表中。将此问题划分为更简单的问题的方法是，再次到单个的节点中去查找。

子问题是这样：“搜索字符串是否与 这个节点 中的字符串相同？”如果是，则您就已经有了答案；如果不是，则更接近了一步。基线条件是什么？有两个：

• 如果当前节点拥有那个字符串，则那就是基线条件（返回“true”）。
• 如果列表为空，则那也是基线条件（返回“false”）。

这个程序不是总能达到第一个基线条件，因为不是总会拥有正在搜索的字符串。不过，我们可以断言，如果程序不能达到第一个基线条件，那么当它到达列表末尾时至少能达到第二个基线条件。

            (define is-in-list
            (lambda   (the-list the-string)
            ;;Check for base case of "list empty"
            (if (null? the-list)
            #f
            ;;Check for base case of "found item"
            (if (equal? the-string (car the-list))
            #t
            ;;Run the algorithm on a smaller problem
            (is-in-list (cdr the-list) the-string)))))
            

这个递归函数能很好地工作，不过它有一个主要的缺点 —— 递归的每一次迭代都要为 the-string 传递 相同的值。传递额外的参数会增加函数调用的开销。

不过，我们可以在函数的起始处设置一个闭包（closure），以使得不再必须为每一个调用都传递那个字符串：

            (define is-in-list2
            (lambda (the-list the-string)
            (letrec
            (
            (recurse (lambda (internal-list)
            (if (null? internal-list)
            #f
            (if (equal? the-string (car internal-list))
            #t
            (recurse (cdr internal-list)))))))
            (recurse the-list))))
            

这个版本的程序稍微难以理解。它定义了一个名为 recurse 的闭包，能够只使用一个参数来调用它，而不是两个。（要获得关于闭包的更多资料，请参阅 参考资料。）我们不必将 the-string 传递给 recurse，因为它已经在父环境（parent environment）中，而且从一个调用到另一个调用时不会改变。由于 recurse 是在 is-in-list2 的 内部 定义的，所以它可以访问所有当前定义的变量，因而不必重新传递它们。这就避免了在每一次迭代时都要传递一个变量。

在这个微不足道的示例中，使用闭包来代替参数传递并没有太多区别，不过，在更为复杂的函数中，这样可以减少很多键盘输入、很多错误以及传递参数中引入的很多开销。

这个示例中所使用的生成递归闭包的方法有些冗长。在递归程序设计中，要一次又一次地以相同的模式使用 letrec 创建递归闭包，并使用一个初始种子值来调用它。

为了让编写递归模式更为简单，Scheme 使用一个名为 命名 let（named let） 的快捷方法。这种快捷方法看起来非常像是一个 let，只是整个程序块会被给定一个名称，这样可以将它作为一个递归闭包去调用。使用命名 let 所构建的函数的参数定义与普通的 let 中的变量类似；初始种子值的设置方式也与普通的 let 中初始变量值的设置方式相同。从那里开始，每一次后续的递归调用都使用那些参数作为新的值。

命名 let 的内容讨论起来相当费解，所以来看下面的代码，并将其与清单 7 中的代码相比较。