第5章递归5.1什么是递归5.1.1递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。若调用自身称之为直接递归。若过程或函数p调用过程或函数9,而q又调用p,称之为间接递归。如果一个递归过程或递归函数中递归调用语句是最后一条执行语句，则称这种递归调用为尾递归。5.1.2何时使用递归在以下三种情况下，常常要用到递归的方法。1.定义是递归的有许多数学公式、数列等的定义是递归的。例如,求nl和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。2.数据结构是递归的有些数据结构是递归的。例如，第2章中介绍过的单链表就是一种递归数据结构,其结点类型定义如下：typedef struct LNodeElemType data;struct LNode *next,LinkList;,该定义中结构体LNode的定义中用到了它自身，即指针域next是一种指向自身类型的指针,所以它是一种递归数据结构。对于递归数据结构采用递归的方法编写算法既方便又有效。例如，求一个不带头结点的单链表head的所有data域（假设为int型）之和的递归算法如下：int Sum(LinkList *head)tif (head=--NULL)return O;elsereturn(head->data+Sum(head->next)33.问题的求解方法是递归的有些问题的解法是递归的,典型的有Hanoi问题求解该问题描述是：设有3个分别命名为X,Y和Z的塔座，在塔座X上有n个直径各不相同,从小到大依次编号为1,2,n的盘片，现要求将X塔座上的n个盘片移到塔座Z上并仍按同样顺序叠放，盘片移动时必须遵守以下规则：每次只能移动一个盘片：盘片可以插在XY和Z中任一塔座：任何时候都不能将个较大的盘片放在较小的盘片上。设计递归求解算法,并将其转换为非递归算法。5.1.3递归模型递归模型是递归算法的抽象它反映一个递归问题的递归结构.例如，前面的递归算法对应的递归模型如下：fun(1)=1(1)fun(n)=n*fun(n-1)n>1 (2)5.2递归算法的设计递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题,通过分别求解41
41 第 5 章 递归 5.1 什么是递归 5.1.1 递归的定义 在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身, 称之为直接递归。若过程或函数 p 调用过程或函数 q,而 q 又调用 p,称之为间接递归。 如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用 为尾递归。 5.1.2 何时使用递归 在以下三种情况下,常常要用到递归的方法。 1. 定义是递归的 有许多数学公式、数列等的定义是递归的。例如,求 n!和 Fibonacci 数列等。这些问题 的求解过程可以将其递归定义直接转化为对应的递归算法。 2. 数据结构是递归的 有些数据结构是递归的。例如,第 2 章中介绍过的单链表就是一种递归数据结构,其结 点类型定义如下： typedef struct LNode { ElemType data; struct LNode *next; } LinkList; 该定义中,结构体LNode的定义中用到了它自身,即指针域next是一种指向自身类型的 指针,所以它是一种递归数据结构。 对于递归数据结构,采用递归的方法编写算法既方便又有效。例如,求一个不带头结点的单链 表 head 的所有 data 域(假设为 int 型)之和的递归算法如下： int Sum(LinkList *head) { if (head==NULL) return 0; else return(head->data+Sum(head->next)); } 3. 问题的求解方法是递归的 有些问题的解法是递归的,典型的有 Hanoi 问题求解,该问题描述是：设有 3 个分别命 名为 X,Y 和 Z 的塔座,在塔座 X 上有 n 个直径各不相同,从小到大依次编号为 1,2,.,n 的盘片, 现要求将 X 塔座上的 n 个盘片移到塔座 Z 上并仍按同样顺序叠放,盘片移动时必须遵守以下 规则：每次只能移动一个盘片；盘片可以插在 X,Y 和 Z 中任一塔座；任何时候都不能将一 个较大的盘片放在较小的盘片上。设计递归求解算法,并将其转换为非递归算法。 5.1.3 递归模型 递归模型是递归算法的抽象,它反映一个递归问题的递归结构,例如,前面的递归算法 对应的递归模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n>1 (2) 5.2 递归算法的设计 递归的求解的过程均有这样的特征：先将整个问题划分为若干个子问题,通过分别求解
子问题，最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法，于是可以再将它们划分成若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。这种自上而下将问题分解、求解，再自上而下引用、合并，求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。递归算法设计先要给出递归模型,再转换成对应的C/C++语言函数。递归设计的步骤如下：(1)对原问题f(s)进行分析,假设出合理的“较小问题”f(s)(与数学归纳法中假设n=k-1时等式成立相似)；(2)假设f(s)是可解的,在此基础上确定f(s)的解,即给出f(s)与f(s)之间的关系(与数学归纳法中求证n=k时等式成立的过程相似)；(3)确定一个特定情况(如f(1)或f(O))的解,由此作为递归出口(与数学归纳法中求证n=1时等式成立相似)。5.3递归算法到非递归算法的转换递归算法有两个基本特性：一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法分析问题的方法是十分有效的：二是递归算法的时间效率通常比较差。因此对求解某些问题时我们希望用递归算法分析问题用非递归算法具体求解问题。这就需要把递归算法转换为非递归算法。把递归算法转化为非递归算法有如下三种基本方法：(1)对于尾递归和单向递归的算法，可用循环结构的算法替代。(2)自己用栈模拟系统的运行时栈，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法。(3)利用栈保存参数，由于栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法。本节讨论第(1)种和第(2)种情况的递归算法转化为非递归算法的问题,前者是一种是直接转化法，不需要使用栈，后者是间接转化法，需要使用栈。第(3)种情况也需要使用栈，但因具体情况而异，例如,在第7章的例7.6就是这种情况的一个例子。5.3.1尾递归和单向递归的消除采用循环结构消除递归没有通用的转换算法，对于具体问题要深入分析对应的递归结构，设计有效的循环语句进行递归到非递归的转换。5.3.2模拟系统的运行时栈消除递归对于不属于尾递归和单向递归的递归算法，很难转化为与之等价的循环算法。但所有的递归程序都可以转化为与之等价的非递归程序（例如,C/C++语言就是先将递归程序转化为非递归程序然后求解的）有一个通用的算法可以将递归程序转化为非递归程序（详见参考文献[2]8.4节),由于这个算法过于通用,比较复杂,不易理解,而且通常需要使用goto转移语句,违反结构化程序设计规定，因此,在这里不作介绍。本章小结本章基本学习要点如下：(1)理解递归的定义和递归模型。(2)重点掌握递归的执行过程。(3)掌握递归设计的一般方法。(4)掌握消除递归的基本方法。(5)灵活运用递归算法解决一些较复杂应用问题。练习教材中p129的习题1和2。42
42 子问题,最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法,于是可以再将 它们划分成若干个子问题,分别求解,如此反复进行,直到不能再划分成子问题,或已经可以求 解为止。这种自上而下将问题分解、求解,再自上而下引用、合并,求出最后解答的过程称为 递归求解过程。这是一种分而治之的算法设计方法。 递归算法设计先要给出递归模型,再转换成对应的 C/C++语言函数。 递归设计的步骤如下： (1)对原问题 f(s)进行分析,假设出合理的“较小问题”f(s')(与数学归纳法中假设 n=k-1 时等式成立相似)； (2)假设f(s')是可解的,在此基础上确定f(s)的解,即给出f(s)与f(s')之间的关系(与数学归 纳法中求证 n=k 时等式成立的过程相似)； (3)确定一个特定情况(如f(1)或 f(0))的解,由此作为递归出口(与数学归纳法中求证 n=1 时等式成立相似)。 5.3 递归算法到非递归算法的转换 递归算法有两个基本特性：一是递归算法是一种分而治之的、把复杂问题分解为简单 问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的；二是递 归算法的时间效率通常比较差。因此,对求解某些问题时,我们希望用递归算法分析问题,用非 递归算法具体求解问题。这就需要把递归算法转换为非递归算法。 把递归算法转化为非递归算法有如下三种基本方法： (1)对于尾递归和单向递归的算法,可用循环结构的算法替代。 (2)自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递归算 法替代递归算法。 (3)利用栈保存参数,由于栈的后进先出特性吻合递归算法的执行过程,因而可以用非 递归算法替代递归算法。 本节讨论第(1)种和第(2)种情况的递归算法转化为非递归算法的问题,前者是一种是 直接转化法,不需要使用栈,后者是间接转化法,需要使用栈。第(3)种情况也需要使用栈,但因 具体情况而异,例如,在第 7 章的例 7.6 就是这种情况的一个例子。 5.3.1 尾递归和单向递归的消除 采用循环结构消除递归没有通用的转换算法,对于具体问题要深入分析对应的递归结构,设 计有效的循环语句进行递归到非递归的转换。 5.3.2 模拟系统的运行时栈消除递归 对于不属于尾递归和单向递归的递归算法,很难转化为与之等价的循环算法。但所有 的递归程序都可以转化为与之等价的非递归程序(例如,C/C++语言就是先将递归程序转化为 非递归程序,然后求解的),有一个通用的算法可以将递归程序转化为非递归程序(详见参考文 献[2]8.4 节),由于这个算法过于通用,比较复杂,不易理解,而且通常需要使用 goto 转移语句,违 反结构化程序设计规定,因此,在这里不作介绍。 本章小结 本章基本学习要点如下： (1)理解递归的定义和递归模型。 (2)重点掌握递归的执行过程。 (3)掌握递归设计的一般方法。 (4)掌握消除递归的基本方法。 (5)灵活运用递归算法解决一些较复杂应用问题。 练习 教材中 p129 的习题 1 和 2