递归详解

计算机科学的新学生通常难以理解递归程序设计的概念。递归思想之所以困难，原因在于它非常像是循环推理（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）。因此，真正的递归函数类似于：

可见，只要初始值大于零，这个函数就能够终止。停止的位置称为 基线条件（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 实现完全相同。

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

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

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

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

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

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

bug 是每位程序员日常生活的一部分，因为就算是最小的循环和最简单的函数调用之中也会有 bug。尽管大部分程序员能够检查代码并测试代码的 bug，但他们并不知道如何证明他们的程序将会按他们所设想的那样去执行。出于此方面的考虑，我们接下来研究 bug 的一些常见来源，然后阐述如何编写正确的程序以及如何证明其正确性。

变量状态改变是产生 bug 的一个主要来源。您可能会认为，程序能敏锐地确切知道变量何时如何改变状态。有时在简单的循环中的确如此，不过在复杂的循环中通常不是这样。通常在循环中给定的变量能够以多种方式改变状态。

例如，如果您拥有一个复杂的 if 语句，有些分支可能会修改某个变量，而其他分支可能会修改其他变量。此外，顺序通常很重要，但是难以绝对保证在所有情形下编码的次序都是正确的。通常，由于这些顺序问题，为某一情形修改某个 bug 会为其他情形引入 bug。

为了预防此类错误，开发人员需要能够：

• 预先断定每个变量如何获得其当前值。
• 确保变量都没有双重用途。（很多程序员经常使用同一变量来存储两个相关但稍有不同的值。）
• 当循环重新开始时，确保所有的变量都处于它们应该处于的状态。（在极少使用和测试的不重要情形中疏忽了为循环变量设置新值，这是常见的程序设计错误。）

为了达成这些目标，我们只需要在程序设计中制定一个规则：一个变量只赋值一次，而且永远不再修改它！

什么？（您说得不可信！）这个规则对很多人来说不可接受，他们所熟知的是命令式、过程式和面向对象程序设计 —— 变量赋值与修改是这些程序设计技术的基础!尽管如此，对命令式语言程序员来说，状态的改变依然是程序设计错误的主要原因。

那么，编程时如何才能不修改变量？让我们来研究一些经常要修改变量的情形，并研究我们是否能够不修改变量而完成任务：

• 重新使用某个变量。
• 变量的条件修改（conditional modification）。
• 循环变量。

我们先来研究第一种情形，重新使用某个变量。通常会出于不同的（但是类似的）目的而重新使用某个变量。例如，有时候，循环的某个部分中，在循环的前半部分需要一个指向当前位置的索引，而循环的其余部分需要一个恰在此索引之前或之后的索引，很多程序员为这两种情况使用同一变量，而只是根据情况对其进行增量处理。当前程序被修改时，这无疑会令程序员难以理解这两种用途。为了预防这一问题，最好的解决方案是创建两个单独的变量，并以同样的方法根据第一个变量得出第二个变量，就像是写入同一变量那样。

第二种情形，即变量的条件修改，是重新使用的问题的一个子集，只是有时我们会保持现有的值，有时需要使用一个新值。同样，最好创建一个新的变量。在大部分语言中，我们可以使用三元运算符 ? : 来设置新变量的值。例如，如果我们需要为新变量赋一个新值，条件是它不大于 some_value，我们可以这样写 int new_variable = old_variable > some_value ? old variable : new_value;。

（我们将在本文中稍后讨论循环变量。）

当我们解决了所有变量状态改变的问题后，就可以确信，当我们第一次定义变量时，变量的定义在函数整个生存期间都会保持。这使得操作的顺序简单了很多，尤其是当修改已有代码时。您不必关心变量被修改的顺序，也不必关心在每一个时刻关于其状态要做什么假定。

当变量的状态不能改变时，在声明它的时刻和地方就给出了其起源的完全定义。您再也不用搜索全部代码去找出不正确的或者混乱的状态。

现在，问题是如何不通过赋值来进行循环？答案是 递归函数。在表 1 中了解循环的特性，看它们可以如何与递归函数的特性相对比。

特性	循环	递归函数
重复	为了获得结果，反复执行同一代码块；以完成代码块或者执行 continue 命令信号而实现重复执行。	为了获得结果，反复执行同一代码块；以反复调用自己为信号而实现重复执行。
终止条件	为了确保能够终止，循环必须要有一个或多个能够使其终止的条件，而且必须保证它能在某种情况下满足这些条件的其中之一。	为了确保能够终止，递归函数需要有一个基线条件，令函数停止递归。
状态	循环进行时更新当前状态。	当前状态作为参数传递。

可见，递归函数与循环有很多类似之处。实际上，可以认为循环和递归函数是能够相互转换的。区别在于，使用递归函数极少被迫修改任何一个变量 —— 只需要将新值作为参数传递给下一次函数调用。这就使得您可以获得避免使用可更新变量的所有益处，同时能够进行重复的、有状态的行为。

让我们来研究一个打印报表的常见循环，了解如何将它转化为一个递归函数。

• 这个循环将在每一个分页处打印出页编号和页眉。
• 假定报告的行依照某个数字标准分组，并假定有用来了解这些组的一个总数。
• 在每一组的最后，打印出组的总数。

出于演示目的，我们略去了所有次要的函数，假定它们存在而且按预期执行。下面是我们的报告打印程序的代码：

				
void print_report(struct report_line *report_lines, int num_lines)
{
   int num_lines_this_page = 0;
   int page_number = 1;
    int current_line; /* iterates through the lines */
    int current_group = 0; /* tells which grouping we are in */
    int previous_group = 0; /* tells which grouping was here on the last loop */
    int group_total = 0; /* saves totals for printout at the end of the grouping */
     print_headings(page_number);
     for(current_line = 0; current_line < num_lines; current_line++)
    {
       num_lines_this_page++;
        if(num_lines_this_page == LINES_PER_PAGE)
       {
          page_number++;
          page_break();
          print_headings(page_number);
       }
       current_group = get_group(report_lines[current_line]);
       if(current_group != previous_group)
       {
         print_totals_for_group(group_total);
          group_total = 0;
       }
        print_line(report_lines[current_line]);
       group_total += get_line_amount(report_lines[current_line]);
    }
}

程序中故意留了一些 bug。看您是否能够找出它们。

由于我们要不断地修改状态变量，所以难以预见在任意特定时刻它们是否正确。下面是递归实现的同一程序：

				
void print_report(struct report_line *report_lines, int num_lines)
{
    int num_lines_this_page = 0;
    int page_number = 1;
    int current_line; /* iterates through the lines */
    int current_group = 0; /* tells which grouping we are in */
    int previous_group = 0; /* tells which grouping was here on the last loop */
    int group_total = 0; /* saves totals for printout at the end of the grouping */
      /* initialize */
   print_headings(page_number);
     /* Seed the values */
    print_report_i(report_lines, 0, 1, 1, 0, 0, num_lines);
}
void print_report_i(struct report_line *report_lines, /* our structure */
    int current_line, /* current index into structure */
    int num_lines_this_page, /* number of lines we've filled this page */
    int page_number,
     int previous_group, /* used to know when to print totals */
    int group_total, /* current aggregated total */
    int num_lines) /* the total number of lines in the structure */
{
    if(current_line == num_lines)
    {
       return;
    }
    else
    {
       if(num_lines_this_page == LINES_PER_PAGE)
       {
          page_break();
          print_headings(page_number + 1);
          print_report_i(
             report_lines,
              current_line,
              1,
              page_number + 1,
              previous_group,
              group_total,
              num_lines);
       }
       else
       {
          int current_group = get_group(report_lines[current_line]);
          if(current_group != previous_group && previous_group != 0)
          {
             print_totals_for_group(group_total);
             print_report_i(
                report_lines,
                 current_line,
                 num_lines_this_page + 1,
                 page_number,
                 current_group,
                 0,
                 num_lines);
          }
          else
          {
             print_line(report_lines[current_line]);
             print_report_i(
                report_lines,
                 current_line + 1,
                 num_lines_this_page + 1,
                 page_number,
                 current_group,
                 group_total + get_line_amount(report_lines[current_line]),
                 num_lines);
          }
       }
    }
}

注意，我们所使用的所有数字都是始终一致的。几乎在任何情形下，只要修改多个状态，在状态改变过程中就会有一些代码行中将不能拥有始终一致的数字。如果以后向程序中此类改变状态的代码中添加一行，而对变量状态的判断与实际情况不相匹配，那么将会遇到很大的困难。这样修改几次以后，可能会因为顺序和状态问题而引入难以捉摸的 bug。在这个程序中，所有状态改变都是通过使用完全前后一致的数据重新运行递归程序而实现的。

尾部递归（Tail-recursive）函数

这样，我已经向您展示了循环与递归函数有何种关联，以及如何将循环转化为递归的、非状态改变的函数，以获得比先前的程序设计可维护性更高而且能够保证正确的成果。

不过，对于递归函数的使用，人们所关心的一个问题是栈空间的增长。确实，随着被调用次数的增加，某些种类的递归函数会线性地增加栈空间的使用 —— 不过，有一类函数，即 尾部递归 函数，不管递归有多深，栈的大小都保持不变。

当我们将循环转化为递归函数时，递归调用是函数所做的最后一件事情。如果仔细观察 print_report_i，您会发现在函数中递归调用之后没有再进一步发生任何事情。

这表现为类似循环的行为。当循环到达循环的末尾，或者它执行 continue 时，那是它在代码块中要做的最后一件事情。同样地，当 print_report_i 再次被调用时，在递归点之后不再做任何事情。

函数所做的最后一件事情是一个函数调用（递归的或者非递归的），这被称为 尾部调用（tail-call）。使用尾部调用的递归称为 尾部递归。让我们来看一些函数调用示例，以了解尾部调用的含义到底是什么：

				
int test1()
{
    int a = 3;
    test1(); /* recursive, but not a tail call.  We continue */
             /* processing in the function after it returns. */
    a = a + 4;
    return a;
}
int test2()
{
    int q = 4;
    q = q + 5;
    return q + test1(); /* test1() is not in tail position.
                         * There is still more work to be
                         * done after test1() returns (like
                         * adding q to the result
                         */
}
int test3()
{
    int b = 5;
     b = b + 2;
     return test1();  /* This is a tail-call.  The return value
                      * of test1() is used as the return value
                      * for this function.
                      */
}
int test4()
{
    test3(); /* not in tail position */
    test3(); /* not in tail position */
    return test3(); /* in tail position */
}

可见，要使调用成为真正的尾部调用，在尾部调用函数返回之前，对其结果 不能执行任何其他操作。

注意，由于在函数中不再做任何事情，那个函数的实际的栈结构也就不需要了。惟一的问题是，很多程序设计语言和编译器不知道如何除去没有用的栈结构。如果我们能找到一个除去这些不需要的栈结构的方法，那么我们的尾部递归函数就可以在固定大小的栈中运行。

在尾部调用之后除去栈结构的方法称为 尾部调用优化。

那么这种优化是什么？我们可以通过询问其他问题来回答那个问题：

• 函数在尾部被调用之后，还需要使用哪个本地变量？哪个也不需要。
• 会对返回的值进行什么处理？什么处理也没有。
• 传递到函数的哪个参数将会被使用？哪个都没有。

好像一旦控制权传递给了尾部调用的函数，栈中就再也没有有用的内容了。虽然还占据着空间，但函数的栈结构此时实际上已经没有用了，因此，尾部调用优化就是要在尾部进行函数调用时使用下一个栈结构 覆盖 当前的栈结构，同时保持原来的返回地址。

我们所做的本质上是对栈进行处理。再也不需要活动记录（activation record），所以我们将删掉它，并将尾部调用的函数重定向返回到调用我们的函数。这意味着我们必须手工重新编写栈来仿造一个返回地址，以使得尾部调用的函数能直接返回到调用它的函数。

这里是为那些真正热衷底层编程的人准备的一个优化尾部调用的汇编语言模板：

				
;;Unoptimized tail-call
my_function:
    ...
    ...
     ;PUSH ARGUMENTS FOR the_function HERE
     call the_function
     ;results are already in %eax so we can just return
    movl %ebp, %esp
    popl %ebp
    ret
;;Optimized tail-call optimized_function:
    ...
    ...
     ;save the old return address
    movl 4(%ebp), %eax
     ;save old %ebp
    movl (%ebp), %ecx
      ;Clear stack activation record (assuming no unknowns like
     ;variable-size argument lists)
    addl $(SIZE_OF_PARAMETERS + 8), %ebp ;(8 is old %ebp + return address))
     ;restore the stack to where it was before the function call
    movl %ebp, %esp
     ;Push arguments onto the stack here
     ;push return address
    pushl %eax
     ;set ebp to old ebp
    movl %ecx, %ebp
     ;Execute the function
     jmp the_function

可见，尾部调用使用了更多一些指令，但是它们可以节省相当多内存。使用它们有一些限制：

• 当函数返回到进行调用的函数时，后者一定不能依赖于仍在栈中的参数列表。
• 调用的函数一定不能顾虑栈指针当前所指的位置。（当然，可以假定它超出了其本地变量的范围。）这意味着您不能使用 -fomit-frame-pointer 进行编译，所有寄存器向栈中保存都要参照 %ebp 而不是 %esp。
• 不能有任何变长的参数列表。

当函数在尾部调用中调用自己时，方法更为简单。我们只需要将参数的新值移到旧值之上，然后在本地变量保存到栈上之后立即进行一个到函数中位置的跳转。由于我们只是跳转到同一个函数，所以返回地址和旧的 %ebp 是相同的，栈的大小也不会改变。因此，在跳转之前我们要做的惟一一件事情就是使用新的参数取代旧的参数。

从而，在只是付出了一些指令的代价后，您的程序会拥有函数式程序的可证明性和命令式程序的速度和内存特性。惟一的问题在于，现在只有非常少的编译器实现了尾部调用优化。Scheme 实现必需要实现这种优化，很多其他函数式语言实现也必须要实现。不过，要注意，由于有时函数式语言使用栈的方式与命令式语言区别很大（或者根本不使用栈），所以实现尾部调用优化的方法可能会有相当大的区别。

最新版本的 GCC 也包含了一些在受限环境下的尾部递归优化。例如，前面描述的 print_report_i 函数在 GCC 3.4 中使用 -O2 进行尾部调用优化编译，因此运行时使用的栈的大小是固定的，而不是线性增长的。

递归是一门伟大的艺术，使得程序的正确性更容易确认，而不需要牺牲性能，但这需要程序员以一种新的眼光来研究程序设计。对新程序员来说，命令式程序设计通常是一个更为自然和直观的起点，这就是为什么大部分程序设计说明都集中关注命令式语言和方法的原因。不过，随着程序越来越复杂，递归程序设计能够让程序员以可维护且逻辑一致的方式更好地组织代码。