精华内容
下载资源
问答
  • java 递归程序实现

    千次阅读 2018-11-11 20:14:15
    java 递归程序实现 本文我们介绍编程语言的一个核心概念————递归。介绍递归功能特性,以及如何使用递归解决不能类型问题。 1. 理解递归 1.1. 递归定义 java中函数调用机制支持方法可以调用自身,这种功能...

    java 递归程序实现

    本文我们介绍编程语言的一个核心概念————递归。介绍递归功能特性,以及如何使用递归解决不能类型问题。

    1. 理解递归

    1.1. 递归定义

    java中函数调用机制支持方法可以调用自身,这种功能称为递归。举例,我们计算求和函数:

    public int sum(int n) {
        if (n >= 1) {
            return sum(n - 1) + n;
        }
        return n;
    }
    

    递归函数有两个主要前提:

    • 终止条件——当一定条件满足时,函数返回特定值,不再递归调用
    • 递归调用——函数调用自身,其输入值更接近终止条件

    每次递归调用都会在jvm栈内存空间中增加栈帧,因此我们不注意递归深度,可能会发生栈内存溢出错误。 我们可以利用尾递归优化进行规避。

    1.2. 尾递归VS头递归

    当递归调用是执行函数的最后部分则称为尾递归,反之为头递归。我们现在通过尾递归方式实现上面的示例:

    public int tailSum(int currentSum, int n) {
        if (n <= 1) {
            return currentSum + n;
        }
        return tailSum(currentSum + n, n - 1);
    }
    

    使用尾递归,递归调用是执行方法中最后需要执行的内容,在当前方法中不再有其他内容需要去执行。因此,理论上无需存储当前函数的栈帧。所以编译器能利用这点优化内存,但java编译器暂时没有针对尾递归进行优化。

    1.3. 递归VS迭代

    递归可以帮助简化解决负责问题,且代码更简洁、可读。但通常需要更多的栈内存以及增加每次递归调用。作为替代方案,能使用递归解决的问题,也可以使用迭代方式实现。下面通过迭代方式实现上面求和的示例:

    public int iterativeSum(int n) {
        int sum = 0;
        if(n < 0) {
            return -1;
        }
        for(int i=0; i<=n; i++) {
            sum += i;
        }
        return sum;
    }
    

    相比于递归,迭代方法性能更好。但迭代更复杂,相比于递归更难理解。例如:遍历二叉树时两种方法对比很明显。

    在头递归、尾递归以及迭代方法中选择最佳方案,取决于特定问题和情况。

    2. 示例实战

    下面我们通过示例使用递归解决几个问题。

    2.1. 求10的n次方

    假如我们需要求10 的n次方。输入为n。通过递归方式实现。首先技术10 的 (n-1)次方,然后乘以10。然后计算10 的 (n-1)次方,即为10 的 (n-2)次方乘以10,以此类推,直到计算(n-n)次方,值为1。java实现代码如下:

    public int powerOf10(int n) {
        if (n == 0) {
            return 1;
        }
        return powerOf10(n-1) * 10;
    }
    

    2.2. 求斐波那契数列的第n个元素值

    从0和1开始,斐波那契数列中每个元素是前两个元素之和:0,1,1,2,3,5,8,13,21,34……
    所以,给定数值n,我们的问题是求第n个元素。使用递归方案,我们需要考虑终止条件以及递归调用。
    还好,两种都非常简单。求n个元素值,只要先求f(n) = f(n-1) + f(n-2) (递归调用)。同时 f(0) = 0 和 f(1) = 1 (终止条件)。那么定义递归方法就比较简单:

    public int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }
    

    2.3 十进制转二进制

    下面我们通过递归方法实现十进制转二进制问题。需求是输入十进制数n,输出二进制字符串。
    方法为十进制数除以2,记录余数继续用商除以2。一直除直到商为0.然后使用倒叙写出所有余数,就获得结果。
    因此,我们的问题是写一个方法按照相反的顺序返回这些余数:

    public String toBinary(int n) {
        if (n <= 1 ) {
            return String.valueOf(n);
        }
        return toBinary(n / 2) + String.valueOf(n % 2);
    }
    

    2.4 计算二叉树高度

    二叉树高度定义为从根到最深叶子节点的边数。我们的问题是计算给定二叉树的高度值。
    一个简单方法是查找最深的叶子,然后计算其到根的边数。使用递归的方案实现,我们重新描述二叉树高度定义————求二叉树中左分支和右分支中最大的高度,然后加一。如果根没有左分支和右分支,其高度为0.

    代码实现为:

    public int calculateTreeHeight(BinaryNode root){
        if (root!= null) {
            if (root.getLeft() != null || root.getRight() != null) {
                return 1 + 
                  max(calculateTreeHeight(root.left), 
                    calculateTreeHeight(root.right));
            }
        }
        return 0;
    }
    

    通过示例,我们看到通过递归方式解决一些问题非常简单。

    3. 总结

    本文我们介绍了java中递归的概念,并演示了几个简单示例。

    展开全文
  • 精通递归程序设计

    千次阅读 2012-05-21 17:11:01
    计算机科学的新学生通常难以理解递归程序设计的概念。递归思想之所以困难,原因在于它非常像是循环推理(circular reasoning)。它也不是一个直观的过程;当我们指挥别人做事的时候,我们极少会递归地指挥他们。 对...

    原文地址:http://www.ibm.com/developerworks/cn/linux/l-recurs.html

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

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

    递归的经典示例

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

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


    清单 1. 阶乘函数的第一次尝试
    				
    int factorial(int n)
    {
       return n * factorial(n - 1);
    }
    

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

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


    清单 2. 实际的递归函数
    				
    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. 合并结果。递归调用之后,我们将当前节点的值加到递归调用的结果上。

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


    清单 3. sum_list 程序的伪代码
    				
     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 实现完全相同。


    清单 4. sum_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 版本同样简单。


    清单 5. sum_list 程序的 C 代码
    				
    int sum_list(struct list_node *l)
    {
       if(l == NULL)
          return 0;
        return l.data + sum_list(l.next);
    }
    

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

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

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

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

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


    清单 6. 确定给定的列表中是否包含给定字符串的 Scheme 代码
    				
    (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),以使得不再必须为每一个调用都传递那个字符串:


    清单 7. 使用闭包的搜索字符串的 Scheme 程序
    				
     (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 中的代码相比较。


    清单 8. 命名 let 示例
    				
    (define is-in-list2
        (lambda (the-list the-string)
           ;;Named Let
           ;;This let block defines a function called "recurse" that is the
          ;;body of this let.  The function's parameters are the same as
           ;;the variables listed in the let.
           (let recurse
              ;;internal-list is the first and only parameter.  The
              ;;first time through the block it will be primed with
              ;;"the-list" and subsequent calls to "recurse" will
              ;;give it whatever value is passed to "recurse"
              ( (internal-list the-list) )
              ;;Body of function/named let block
              (if (null? internal-list)
                 #f
                 (if (equal? the-string (car internal-list))
                    #t
                    ;;Call recursive function with the
                    ;;rest of the list
                    (recurse (cdr internal-list)))))))
    

    在编写递归函数时,命名 let 能够相当程度地减少键盘输入以及出现错误的数量。如果您理解命名 let 的概念仍有困难,那么我建议您对上面的两个程序中的每一行进行全面的比较(另外参阅本文 参考资料 部分中的一些文档)。

    我们的下一个基于列表的递归函数示例要稍微复杂一些。它将检查列表是否以升序排序。如果列表是以升序排序,则函数返回 #t;否则,它将返回 #f。这个程序稍有不同,因为除了必须要考查当前的值以外,我们还必须记住处理过的最后一个值。

    对列表中第一项的处理必须与其他项不同,因为没有在它之前的任何项。对于其余的项,我们需要将先前考查的值传递到函数调用中。函数类似如下:


    清单 9. 确定列表是否以升序排序的 Scheme 程序
    				
    (define is-ascending
        (lambda (the-list)
           ;;First, Initialize the algorithm.  To do this we
           ;;need to get the first value, if it exists, and
           ;;use it as a seed to the recursive function
           (if (null? the-list)
              #t
              (let is-ascending-recurse
                 (
                     (previous-item (car the-list))
                    (remaining-items (cdr the-list))
                 )
                 ;;Base case #1 - end of list
                 (if (null? remaining-items)
                    #t
                    (if (< previous-item (car remaining-items))
                       ;;Recursive case, check the rest of the list
                       (is-ascending-recurse (car remaining-items) (cdr remaining-items))
                       ;;Base case #2 - not in ascending order
                       #f))))))
    

    这个程序首先检查边界条件 —— 列表是否为空。空列表被认为是升序的。然后程序以列表中的第一项及其余部分列表为种子开始递归函数。

    然后检查基线条件。能到达列表末尾的惟一情形是此前所有项都按顺序排列,所以,如果某个列表为空,则列表为升序。否则,我们去检查当前项。

    如果当前项是升序的,那么我们接下来只需要解决问题的一个子集 —— 列表的其余部分是否为升序。所以我们递归处理列表其余部分,并再次尝试。

    注意在函数中我们是如何通过向前传递程序来保持函数调用过程中的状态的。以前我们每次只是传递了列表的剩余部分。不过,在这个函数中,我们需要了解关于计算状态的稍多些内容。当前计算的结果依赖于之前的部分结果,所以,在每次后续递归调用中,我们向前传递那些结果。对更复杂的递归过程来说这是一个通用的模式。

    编写保证正确的程序

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

    bug 来源:状态改变

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

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

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

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

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

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

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

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

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

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

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

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

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

    什么是循环变量?

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

    表 1. 对比循环与递归函数

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

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

    将一个常见的循环转化为递归函数

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

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

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


    清单 10. 用普通循环实现的报告打印程序
    				
    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。看您是否能够找出它们。

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


    清单 11. 使用递归实现的报告打印程序
    				
    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。在这个程序中,所有状态改变都是通过使用完全前后一致的数据重新运行递归程序而实现的。

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

    由于从来没有改变变量的状态,所以证明您的程序非常简单。让我们来研究关于清单 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. 证明对于任意给定的一组行,程序都能终止

    假定
    我们假定 num_lines >= current_lineLINES_PER_PAGE > 1
    基线条件证明
    通过观察,我们可以知道,当 current_line == num_lines 时,程序会立即终止。
    归纳步骤证明
    在程序的每一次迭代中,current_line 或者增 1(R3),或者保持不变(R2 和 R3)。

    只有当 current_line 的当前值与 current_line 的先前值不同时,R2 才会发生,因为 current_groupprevious_group 直接由它派生而来。

    只有 num_lines_this_page 中的变化会令 R1 发生,而这种变化只能由 R2 和 R3 产生。

    由于只有以 R3 为基础才能发生 R2,且只有以 R2 和 R3 为基础才能发生 R1,我们可以断定,current_line 必须是增加的,而且只能是单调递增。

    因此,如果 current_line 的某一值可以终止,那么 current_line 之前的所有值都可以终止。

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

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

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

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

    假定
    当前页的第一行已经打印了一个页眉。
    定理 1
    如果 num_lines_this_page 设置为正确起始值(条件 1),每打印一行 num_lines_per_page 增 1(条件 2),并且在分页之后重新设置 num_lines_per_page(条件 3),那么 num_lines_per_page 则精确地表示此页上已经打印的行数。
    定理 2
    如果 num_lines_this_page 精确地表示已经打印的行数(条件 1),并且每当 num_lines_this_page == LINES_PER_PAGE 时执行一次分页,那么我们就确信我们的程序在打印 LINES_PER_PAGE 行之后会进行一次分页。
    证明
    设想定理 1 的条件 1。如果我们假定通过 print_report 调用 print_report_i,那么观察可知,这无论如何都是显然的。

    通过确认每一个打印一行的过程都相应使 num_lines_this_page 增 1,条件 2 能得到确定。在以下三种情况下完成行打印:

    1. 打印组的总数。
    2. 打印单个的报告行。
    3. 打印页眉。

    观察可见,行打印条件 1 和 2 将 num_lines_this_page 增 1,行打印条件 3 在一个 分页/页眉 组合打印之后将 num_lines_this_page 重新设置为适当的值(常规的条件 3)。定理 1 的要求得到了满足,所以我们就已经证明了程序会在打印 LINES_PER_PAGE 行之后进行一次分页。

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

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

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

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

    假定
    由于我们要使用证明 1,所以这个证明依赖于证明 1 的假定。另外我们假定 print_report_i 的第一次调用来自于 print_report,这表示 current_line 从 0 开始。
    定理 1
    如果 current_line 只有在一次 print_line(条件 1)调用之后才会增加,而且只有在 current_line 增加之前才会调用 print_line,那么 current_line 每经历一个数字将会打印出单独的一行。
    定理 2
    如果定理 1 为真(条件 1),同时 current_line 经历从 0 到 num_lines - 1 的每一个数字(条件 2),而且当 current_line == num_lines 时终止(条件 3),那么每一个报告项的行都严格只打印一次。
    证明
    观察可知,定理 1 的条件 1 和条件 2 为真。R3 是惟一一处 current_line 会增加的地方,而且这个增加在 print_line 的调用之后随即就会发生。因此,定理 1 可证,同样定理 2 的条件 1 可证。

    通过归纳可以证明条件 2 和 3,并且,实际上这只是第一个终止证明的重复。我们可以使用终止的证明来最终证明条件 3。基于那个证明,以及 current_line 从 0 开始的假定,条件 2 为真。因此,我们已经证明报告的每一行都严格只打印一次。

    证明和递归程序设计

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

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

    尾部递归(Tail-recursive)函数

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

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

    尾部递归

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

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

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


    清单 12. 尾部调用和非尾部调用
    				
    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),所以我们将删掉它,并将尾部调用的函数重定向返回到调用我们的函数。这意味着我们必须手工重新编写栈来仿造一个返回地址,以使得尾部调用的函数能直接返回到调用它的函数。

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


    清单 13. 尾部调用的汇编语言模板
    				
    ;;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 进行尾部调用优化编译,因此运行时使用的栈的大小是固定的,而不是线性增长的。

    结束语

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


    展开全文
  • 栈 当我们在运行递归函数时,有的同学一上来就给这个函数进行一个深度递归,成功运行还好,但是一旦...如图所示,该程序运行到38时,出现错误,并没有一直进行到1,这是为什么呢? 原因:在深度递归的过程中,每一...

    栈的溢出

    当我们在运行递归函数时,有的同学一上来就给这个函数进行一个深度递归,成功运行还好,但是一旦不成功则会使栈蹦掉,入下面的一个深度递归的程序。
    在这里插入图片描述
    这个函数描述的内容为分别显示出数与其地址。接下来,让我们来运行这个程序。
    在Linux重,不输入任何参数则默认的是100,输出100到1的地址。
    在这里插入图片描述
    如图所示,该程序运行到38时,出现错误,并没有一直进行到1,这是为什么呢?

    • 原因】:在深度递归的过程中,每一步都在不断地使用栈空间,运行到38时栈空间已经不足,所以这时无法再进行下一步37的递归,栈空间蹦掉,所以出现错误。

    • 总结】:在写递归函数时,不要上头,过度的递归会使你的栈承受不起。

    展开全文
  • 精通递归程序设计

    千次阅读 2005-12-19 19:35:00
    精通递归程序设计内容:递归的经典示例递归程序的基本步骤编写保证正确的程序尾部递归(Tail-recursive)函数结束语参考资料 关于作者对本文的评价相关内容:高阶函数XML 问题: 研究 SXML 和 SSAX可爱的 Python: ...
     
    
    精通递归程序设计
    内容:
    递归的经典示例
    递归程序的基本步骤
    编写保证正确的程序
    尾部递归(Tail-recursive)函数
    结束语
    参考资料
    关于作者
    对本文的评价
    相关内容:
    高阶函数
    XML 问题: 研究 SXML 和 SSAX
    可爱的 Python: Python 中的函数编程
    Java 语言中的函数编程
    更佳编程之路: 第四章
    Haskell 入门
    Use recursion effectively in XSL
    订阅:
    developerWorks 时事通讯
    理解递归,以编写可维护的、一致的、保证正确的代码

    级别: 中级

    Jonathan Bartlett
    技术主管, New Media Worx
    2005 年 7 月 11 日

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

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

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

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

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

    清单 1. 阶乘函数的第一次尝试
    
    int factorial(int n)
    {
       return n * factorial(n - 1);
    }
    

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

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

    清单 2. 实际的递归函数
    
    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. 合并结果。递归调用之后,我们将当前节点的值加到递归调用的结果上。

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

    清单 3. sum_list 程序的伪代码
    
     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 实现完全相同。

    清单 4. sum_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 版本同样简单。

    清单 5. sum_list 程序的 C 代码
    
    int sum_list(struct list_node *l)
    {
       if(l == NULL)
          return 0;
        return l.data + sum_list(l.next);
    }
    

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

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

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

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

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

    清单 6. 确定给定的列表中是否包含给定字符串的 Scheme 代码
    
    (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),以使得不再必须为每一个调用都传递那个字符串:

    清单 7. 使用闭包的搜索字符串的 Scheme 程序
    
     (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 中的代码相比较。

    清单 8. 命名 let 示例
    
    (define is-in-list2
        (lambda (the-list the-string)
           ;;Named Let
           ;;This let block defines a function called "recurse" that is the
          ;;body of this let.  The function's parameters are the same as
           ;;the variables listed in the let.
           (let recurse
              ;;internal-list is the first and only parameter.  The
              ;;first time through the block it will be primed with
              ;;"the-list" and subsequent calls to "recurse" will
              ;;give it whatever value is passed to "recurse"
              ( (internal-list the-list) )
    
              ;;Body of function/named let block
              (if (null? internal-list)
                 #f
                 (if (equal? the-string (car internal-list))
                    #t
                    ;;Call recursive function with the
                    ;;rest of the list
                    (recurse (cdr internal-list)))))))
    

    在编写递归函数时,命名 let 能够相当程度地减少键盘输入以及出现错误的数量。如果您理解命名 let 的概念仍有困难,那么我建议您对上面的两个程序中的每一行进行全面的比较(另外参阅本文 参考资料 部分中的一些文档)。

    我们的下一个基于列表的递归函数示例要稍微复杂一些。它将检查列表是否以升序排序。如果列表是以升序排序,则函数返回 #t;否则,它将返回 #f。这个程序稍有不同,因为除了必须要考查当前的值以外,我们还必须记住处理过的最后一个值。

    对列表中第一项的处理必须与其他项不同,因为没有在它之前的任何项。对于其余的项,我们需要将先前考查的值传递到函数调用中。函数类似如下:

    清单 9. 确定列表是否以升序排序的 Scheme 程序
    
    (define is-ascending
        (lambda (the-list)
           ;;First, Initialize the algorithm.  To do this we
           ;;need to get the first value, if it exists, and
           ;;use it as a seed to the recursive function
           (if (null? the-list)
              #t
              (let is-ascending-recurse
                 (
                     (previous-item (car the-list))
                    (remaining-items (cdr the-list))
                 )
                 ;;Base case #1 - end of list
                 (if (null? remaining-items)
                    #t
                    (if (< previous-item (car remaining-items))
                       ;;Recursive case, check the rest of the list
                       (is-ascending-recurse (car remaining-items) (cdr remaining-items))
                       ;;Base case #2 - not in ascending order
                       #f))))))
    

    这个程序首先检查边界条件 —— 列表是否为空。空列表被认为是升序的。然后程序以列表中的第一项及其余部分列表为种子开始递归函数。

    然后检查基线条件。能到达列表末尾的惟一情形是此前所有项都按顺序排列,所以,如果某个列表为空,则列表为升序。否则,我们去检查当前项。

    如果当前项是升序的,那么我们接下来只需要解决问题的一个子集 —— 列表的其余部分是否为升序。所以我们递归处理列表其余部分,并再次尝试。

    注意在函数中我们是如何通过向前传递程序来保持函数调用过程中的状态的。以前我们每次只是传递了列表的剩余部分。不过,在这个函数中,我们需要了解关于计算状态的稍多些内容。当前计算的结果依赖于之前的部分结果,所以,在每次后续递归调用中,我们向前传递那些结果。对更复杂的递归过程来说这是一个通用的模式。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    表 1. 对比循环与递归函数

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

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

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

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

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

    清单 10. 用普通循环实现的报告打印程序
    
    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。看您是否能够找出它们。

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

    清单 11. 使用递归实现的报告打印程序
    
    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。在这个程序中,所有状态改变都是通过使用完全前后一致的数据重新运行递归程序而实现的。

    递归的报告打印程序的证明
    由于从来没有改变变量的状态,所以证明您的程序非常简单。让我们来研究关于清单 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. 证明对于任意给定的一组行,程序都能终止

    假定
    我们假定 num_lines >= current_lineLINES_PER_PAGE > 1
    基线条件证明
    通过观察,我们可以知道,当 current_line == num_lines 时,程序会立即终止。
    归纳步骤证明
    在程序的每一次迭代中,current_line 或者增 1(R3),或者保持不变(R2 和 R3)。

    只有当 current_line 的当前值与 current_line 的先前值不同时,R2 才会发生,因为 current_groupprevious_group 直接由它派生而来。

    只有 num_lines_this_page 中的变化会令 R1 发生,而这种变化只能由 R2 和 R3 产生。

    由于只有以 R3 为基础才能发生 R2,且只有以 R2 和 R3 为基础才能发生 R1,我们可以断定,current_line 必须是增加的,而且只能是单调递增。

    因此,如果 current_line 的某一值可以终止,那么 current_line 之前的所有值都可以终止。

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

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

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

    假定
    当前页的第一行已经打印了一个页眉。
    定理 1
    如果 num_lines_this_page 设置为正确起始值(条件 1),每打印一行 num_lines_per_page 增 1(条件 2),并且在分页之后重新设置 num_lines_per_page(条件 3),那么 num_lines_per_page 则精确地表示此页上已经打印的行数。
    定理 2
    如果 num_lines_this_page 精确地表示已经打印的行数(条件 1),并且每当 num_lines_this_page == LINES_PER_PAGE 时执行一次分页,那么我们就确信我们的程序在打印 LINES_PER_PAGE 行之后会进行一次分页。
    证明
    设想定理 1 的条件 1。如果我们假定通过 print_report 调用 print_report_i,那么观察可知,这无论如何都是显然的。

    通过确认每一个打印一行的过程都相应使 num_lines_this_page 增 1,条件 2 能得到确定。在以下三种情况下完成行打印:

    1. 打印组的总数。
    2. 打印单个的报告行。
    3. 打印页眉。

    观察可见,行打印条件 1 和 2 将 num_lines_this_page 增 1,行打印条件 3 在一个 分页/页眉 组合打印之后将 num_lines_this_page 重新设置为适当的值(常规的条件 3)。定理 1 的要求得到了满足,所以我们就已经证明了程序会在打印 LINES_PER_PAGE 行之后进行一次分页。

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

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

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

    假定
    由于我们要使用证明 1,所以这个证明依赖于证明 1 的假定。另外我们假定 print_report_i 的第一次调用来自于 print_report,这表示 current_line 从 0 开始。
    定理 1
    如果 current_line 只有在一次 print_line(条件 1)调用之后才会增加,而且只有在 current_line 增加之前才会调用 print_line,那么 current_line 每经历一个数字将会打印出单独的一行。
    定理 2
    如果定理 1 为真(条件 1),同时 current_line 经历从 0 到 num_lines - 1 的每一个数字(条件 2),而且当 current_line == num_lines 时终止(条件 3),那么每一个报告项的行都严格只打印一次。
    证明
    观察可知,定理 1 的条件 1 和条件 2 为真。R3 是惟一一处 current_line 会增加的地方,而且这个增加在 print_line 的调用之后随即就会发生。因此,定理 1 可证,同样定理 2 的条件 1 可证。

    通过归纳可以证明条件 2 和 3,并且,实际上这只是第一个终止证明的重复。我们可以使用终止的证明来最终证明条件 3。基于那个证明,以及 current_line 从 0 开始的假定,条件 2 为真。因此,我们已经证明报告的每一行都严格只打印一次。

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

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

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

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

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

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

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

    清单 12. 尾部调用和非尾部调用
    
    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),所以我们将删掉它,并将尾部调用的函数重定向返回到调用我们的函数。这意味着我们必须手工重新编写栈来仿造一个返回地址,以使得尾部调用的函数能直接返回到调用它的函数。

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

    清单 13. 尾部调用的汇编语言模板
    
    ;;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 进行尾部调用优化编译,因此运行时使用的栈的大小是固定的,而不是线性增长的。

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

    参考资料

    关于作者
    Jonathan Bartlett 是 Programming from the Ground Up 一书的作者,这本书介绍的是使用 Linux 汇编语言进行程序设计。他是 New Media Worx 的首席开发人员,为客户开发 Web、视频、自助服务(kiosk)以及桌面应用程序。通过 johnnyb@eskimo.com 与 Jonathan 联系。
    展开全文
  • 编译原理递归程序语法分析

    千次阅读 2018-11-28 22:07:47
    高级程序设计语言的语法规则通常都是用上下文无关文法来描述的,文法中的符号分为终结符号和非终结符号。 本分析程序所分析的文法如下: G[E]: E→eBaA A→a|bAcB B→dEd|aC C→e|dC 可以求...
  • 牛客网编程提示“程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)“的可能原因
  • 语法分析器之递归程序

    千次阅读 2016-10-25 21:58:42
    表达式语法分析——递归程序递归程序法是一种确定的自顶向下语法分析方法,要求文法是LL(1)文法。它的实现思想是对应文法中每个非终结符编写一个递归过程,每个过程的功能是识别由该非终结符推出的串,当某...
  • 编译原理-递归程序

    千次阅读 2017-12-05 21:54:43
    0x01 题目描述递归程序法是一种确定的自顶向下语法分析方法,要求文法是LL(1)文法。它的实现思想是对应文法中每个非终结符编写一个递归过程,每个过程的功能是识别由该非终结符推出的串,当某非终结符的产生式有多...
  • 递归

    千次阅读 2016-04-22 11:57:39
    递归方法具有易于描述、证明简单等优点,在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用,是许多复杂算法的基础。 递归概念 一个函数在它的函数体内调用它自身称为递归(recursion)调用。是一个...
  • 表达式语法分析——递归程序

    千次阅读 2016-10-14 21:31:01
    表达式语法分析——递归程序法 Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Problem Description   递归程序法是一种确定的自顶向下语法分析方法,要求文法是LL(1)文法。它的实现思想是...
  • 轻轻松松学递归

    千次阅读 多人点赞 2019-09-05 12:54:33
    一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算...
  • 算法精解-C语言描述 递归和尾递归 (图解+实例)

    千次阅读 多人点赞 2017-10-19 06:07:23
    递归是一种强大的方法,它允许一个对象以其自身更小的形式来定义自己。 让我们来观察一下自然界中出现的递归现象:蕨类植物的叶子,每片叶子叶脉中的小分支都是整片叶子的较小缩影;又或者两个反光的物体,相互映射...
  • 试编写一段递归程序计算ackermann函数ACK(m,n)。对于m≥0和n≥0的ACK(m,n)函数定义如下: ACK(0,n)=n+1 ACK(m,0)=ACK(m-1,1) ACK(m,n)=ACK(m-1,ACK(m,n-1)) 程序要求: ⑴ m、n在主程序从键盘输入,输入错误显示...
  • 本资源文档中有对PL/0的函数调用关系图。通过阅读和改造PL/0编译程序,熟悉PL...掌握递归下降语法分析程序的设计思想,加深对递归下降语法分析程序的理解。通过设计编制调试具体的YACC程序,掌握YACC源程序的基本组成。
  • 我的代码,调了很久,提示程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多),为什么啊,这程序很耗堆栈空间么,不懂。。。。。。求解 #include <stdio.h> #include <stdlib.h> #...
  • 这一节我们来讨论递归函数栈帧实现、
  • OJ题目描述 输入一个链表,从尾到头打印链表每个节点的值。 代码: ------ ```c /** ...段错误:您的程序发生段错误,可能是数组越界,堆栈溢出(比如,递归调用层数太多)等情况引起
  • SQLSTATE SQL SERVER 驱动程序错误描述

    千次阅读 2013-10-06 09:37:55
    HY000   所有绑定列都是只读的。   必须是可升级的列,以使用 SQLSetPos 或 SQLBulkOperations 更改或插入行。...请删除并重新启动应用程序。...驱动程序请求一个较新的 ...问题可能出在应用程序当前目录中的 netli
  • 表达式语法分析——递归程序法 Time Limit: 1000 ms Memory Limit: 65536 KiB Problem Description 递归程序法是一种确定的自顶向下语法分析方法,要求文法是LL(1)文法。它的实现思想是对应文法中每个非终结符...
  • 递归入门

    千次阅读 多人点赞 2012-11-23 17:35:45
    写在前面: 对于强大的递归。要想做到灵活运用,是需要花时间进行练习并总结。往往递归学习的入门也是难度也...在此推荐一本学习递归较好的的入门书:《程序设计抽象思想:C语言描述》 。本文章也引用了书中的对递
  • 完成以下描述赋值语句的LL(1)文法的递归下降分析程序 G[S]: S→V=E E→TE′ E′→ATE′|ε T→FT′ T′→MFT′|ε F→ (E)|i A→+|- M→*|/ V→i 2、[设计说明] 终结符号i为用户定义的简单变量,即...
  • 递归转非递归几个实例

    千次阅读 2014-05-27 22:58:46
    在要求高效的很多场合需要将递归程序改写成非递归程序,由于疏于梳理这方面的知识点,感觉对于有些递归结构有些力不从心,于是有意识的学习了一下,感觉好了很多。  关于递归程序转非递归程序,基本通用方法是用...
  • 递归调用

    2015-07-19 14:35:36
    今天cf遇见了一点问题,是自己学过却不怎么熟悉的递归调用。...这种功能为递归结构问题提供了求解的实现手段,使程序语言的描述与问题的自然描述完全一直,因而使程序易于理解、易于维护。  通过简单的例子说明递归
  • 程序错误类型及其处理

    千次阅读 2017-07-26 17:08:56
    程序错误指的是程序库实现错误,当然,程序库的提供者在程序库发布之前,肯定想尽可能多地检测和纠正错误,但是任何比较大的程序库在发布的时候,都是肯定会包含错误的。用户错误主要是用户操作不当,指如何使用...
  • 二叉树递归遍历与非递归遍历

    千次阅读 2015-07-23 21:10:11
    二叉树递归遍历与非递归遍历 二叉树递归遍历与非递归遍历 引言 递归式遍历 前序遍历 中序遍历 后序遍历 非递归式遍历 前序遍历 中序遍历 后序遍历 一种更简单的非递归式遍历 前序遍历 中序遍历 后序遍历 ...
  • Scala中尾递归

    千次阅读 2014-07-17 17:17:21
     作为一个程序员,大家对递归应该都很熟悉,在《 数据结构与算法分析:C描述》书中,已打印链表为例,提到了尾递归,并指出了尾递归是对递归及其不当的使用,它指出虽然编译器会对递归进行自动优化,但是一般情况下...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 84,806
精华内容 33,922
关键字:

对于递归程序的描述错误的是