精通递归程序设计

内容摘要 理解递归，以编写可维护的、一致的、保证正确的代码

递归的报告打印程序的证明

由于从来没有改变变量的状态，所以证明您的程序非常简单。让我们来研究关于清单 11 中报告打印程序的一些特性证明。

提示那些大学毕业后没有进行过程序证明的人（或者可能从来没有进行过），进行程序证明，基本上就是寻找程序的某个特性（通常指定为 P），并证明那个特性适用。要完成此任务需要使用：

• 公理（axioms），假定的真理。
• 定理（theorems） 由公理推论得到的关于程序的陈述。

目标是将公理与定理联合起来证明特性 P 为真。如果程序有不只一个特性，则通常分别去证明每一个。由于这个程序有若干个特性，我们将为其中一些给出简短的证明。

由于我们在进行不正式的证明，所以我不会为所使用的公理命名，也不会尝试去证明那些用来令证明有效的中间定理。但愿它们足够明显，以致不必对它们进行证明。

在证明过程中，我将把程序的三个递归点分别称为 R1、R2 和 R3。所有程序都有一个隐式的假设：report_lines 为合法的指针，且 num_lines 准确地反映 report_lines 所显示的行数。

在示例中，我将尝试去证明：

• 任意给定的一组行，程序都能终止。
• 在 LINES_PER_PAGE 行之后会发生分页。
• 每一个报告项都严格只打印一次。

证明程序会终止

此证明将确认对于任意给定的一组行，程序都会终止。这个证明将使用一种在递归程序中常见的证明技术，名为 归纳证明（inductive proof）。

归纳证明由两个步骤构成。首先，需要证明特性 P 对于给定的一组参数是适用的。然后去证明一个归纳，表明如果 P 对于 X 的值适用，那么它对于 X + 1（或者 X - 1，或者任意类型的步进处理）的值也必须适用。通过这种方法您就可以证明特性 P 适用于从已经证明的那个数开始依次连续的所有数。

在这个程序中，我们将证明 print_report_i 会在 current_line == num_lines 的条件下终止，然后证明如果 print_report_i 会在给定的 current_line 条件下终止，那么它也可以在 current_line - 1 条件下终止，假定 current_line > 0。

证明 1. 证明对于任意给定的一组行，程序都能终止

我们现在已经证明，在我们的假设前提下，print_report_i 将可以终止。

证明在 LINES_PER_PAGE 行之后会发生分页

这个程序会保持在何处分页的追踪，因此，有必要证明分页机制有效。如前所述，证明以公理和定理做为其论据。在此，我将提出两个定理来完成证明。如果定理的条件被证明为真，则我们可以使用此定理来确定我们的程序的定理结果的正确性。

证明 2. 在 LINES_PER_PAGE 行之后发生分页

证明每一个报告项都严格只打印一次

我们需要确保程序总是打印报告的每一行，从不遗漏。我们可以使用一个归纳证明来证明，如果 print_report_i 根据 current_line == X 准确地打印一行，那么它也将或者准确地打印一行，或者因 current_line == X + 1 而终止。另外，由于我们既有起始条件也有终止条件，所以我们必须证明两者都是正确的，因此我们必须证明那个基线条件，即当 current_line == 0 时 print_report_i 有效，而当 current_line == num_lines 时它 只是 会终止。

不过，在本例中，我们可以进行相当程度的简化，只是通过补充我们的第一个证明来给出一个直接证明。我们的第一个证明表明，在起始时使用一个给定的数字，将在适当的时候终止程序。通过观察可知，算法继续进行，证明已经完成了一半。

证明 3. 每一个报告项的行都严格只打印一次

证明和递归程序设计

这些只是我们能为程序所做的一些证明。它们还可以更为严格，不过我们大部分人选择的是程序设计而非数学，因为我们不能忍受数学的单调，也不能忍受它的符号。

使用递归可以极度简化程序的核查。并不是不能为命令式程序进行那种程序证明，而是状态改变发生的次数之多使得那些证明不具意义。使用递归程序，用递归取代修改状态，状态改变发生的次数很少，并且，通过一次设置所有递归变量，程序变更能保持前后一致。这不能完全避免逻辑错误，但它确实可以消除其中很多种类的错误。这种只使用递归来完成状态改变和重复的程序设计方法通常被称作 函数式程序设计（functional programming）。

尾部递归（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 进行尾部调用优化编译，因此运行时使用的栈的大小是固定的，而不是线性增长的。

结束语

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

参考资料

• 您可以参阅本文在 developerWorks 全球站点上的 英文原文。
  
  
• How to Design Programs （MIT Press，2001）是使用函数式编程进行程序设计的极好介绍，其中涉及了很多递归技术。
  
  
• Structure and Interpretation of Computer Programs （MIT Press，1996）是一个难度更大的介绍，但是它更有深度。
  
  
• 要从栈的角度来理解递归程序的问题，需要一些汇编语言如何工作的知识； Programming from the Ground Up （Bartlett Press，2004）是一份合适的资料。
  
  
• 这个站点提供了 关于递归的更多可运行示例，其中包括教程，每一章展开一个特定的主题，每一节由解决的各种特定问题构成。
  
  
• 对于那些很久没有或者根本没有进行过证明的人而言，这里是一个关于编写证明的实用介绍。
  
  
• 如果您需要另外的关于归纳证明的解释，请参考 这个关于数学归纳的教程。
  
  
• 您可能还不知道 证明也有模式。
  
  
• 高阶函数 （developerWorks，2005 年 3 月）研究了闭包以及其他与 Scheme 相关的函数。
  
  
• XML 问题: 研究 SXML 和 SSAX（developerWorks，2003 年 10 月）研究的是使用 Scheme 递归特性来处理 XML。
  
  
• 可爱的 Python: Python 中的函数编程系列文章（developerWorks，2001 年 3 月）论述的是，尽管程序员可能会认为 Python 是过程的和面向对象的语言，但它实际上包含了使用完整的函数式方法进行程序设计所需要的所有内容。
  
  
• Java 语言中的函数编程 （developerWorks，2004 年 7 月）向您展示了，如何使用闭包和高阶函数等函数式程序设计结构来使用 Java 语言编写构架适宜的、模块化的代码。
  
  
• 更佳编程之路: 第四章 （developerWorks，2002 年 1 月）介绍了函数式程序设计的概念，因为这与 Perl 有关系。
  
  
• Haskell 入门（developerWorks，2001 年 9 月）为命令式语言开发者提供了一个关于函数式程序设计（集中关注 Haskell 98）的适度的介绍。
  
  
• Use recursion effectively in XSL（developerWorks，2002 年 10 月）阐述的是，要有效且高效地使用 XSL 转换，需要理解如何使用 XSL 作为函数式语言，这也就意味着要理解递归。
  
  
• 在 developerWorks Linux 专区 可以找到更多为 Linux 开发者准备的参考资料。
  
  
• 通过参与 developerWorks blogs 加入 developerWorks 社区。
  
  
• 在 Developer Bookstore Linux 专区购买 打折出售的 Linux 书籍。
  
  
• 定购免费的 SEK for Linux，在这套 DVD 中（两张），包含了来自 DB2®、Lotus®、Rational®、 Tivoli® 和 WebSphere® 的最新的用于 Linux 的 IBM 试用软件。
  
  
• 使用可以直接从 developerWorks 下载的 IBM 试用软件 来改革您的下一个 Linux 开发项目。
  

关于作者

		Jonathan Bartlett 是 Programming from the Ground Up 一书的作者，这本书介绍的是使用 Linux 汇编语言进行程序设计。他是 New Media Worx 的首席开发人员，为客户开发 Web、视频、自助服务（kiosk）以及桌面应用程序。通过 johnnyb@eskimo.com 与 Jonathan 联系。

[1] [2]

责任编辑 webmaster

相关链接