数据结构6递归

1、复习,一、常见特殊矩阵的存储规律： 对称矩阵、上(下)三角矩阵、对角矩阵、三对角矩阵 二、稀疏矩阵的处理 存储结构： - 非零元的表示：三元信息组(r,c,d) - 行逻辑连接的顺序表表示 - 十字链表 应用：矩阵的转置(两种算法)、矩阵相乘、一元或多元多项式运算,第六章 递 归,递归是解决计算机和数学问题的一个有效工具，同时也是一种化繁为简的思维方式。在程序设计语言中可以用它来定义语言的语法，在数据结构中可以用它来编制表和树结构的查找和排序算法。递归也应用在组合数学领域用来处理计数和可能性问题。无论在理论还是在实际应用方面，递归都是算法研究、博弈论和图论的重要课题。 在软件设计中递归是一个重

2、要的算法设计方法和技术，递归子程序是通过调用自身来完成与自身要求相同的子问题的求解，并利用系统内部功能自动实现调用过程中信息的保存与恢复，因而省略了程序设计中的许多细节操作，简化了程序设计过程，使程序设计人员可以集中注意力于主要问题的求解上。,6.1 什么是递归 6.1.1 递归的定义 在定义一个过程或函数时出现调用本过程或本函数的成分，称之为递归。 递归就是一个事件或对象部分由自己组成，或者按它自己定义。,一般程序调用：,递归程序调用：,程序proc 调用程序proc return,递归程序也必须有出口，其过程比较繁琐。递归问题举例：,例6.1 定义一个人的后代概念如下： 这个人的子女是它的

3、后代； 这个人的子女的后代也是他的后代。 即定义后代概念时有使用了这个概念。,一、递归算法的组成 函数或过程直接或间接调用自己的算法称为递归算法。递归算法包括： 递推：就是为得到问题的解，将其推倒比原来问题简单的问题的求解。使用递推时应注意到，递推应有终止之时。 如求n!：,这里的 n=0，即 0!=1为递推的终止条件。 回归：就是指当“简单问题得到解后，回归到原问题的解上”。 如在求n!时，当计算完(n-1)!后，回归到计算n(n-1)上。但是在使用回归时应注意，递归算法所涉及的参数与局部变量是有层次的。 回归并不引起其他动作。,二、递归方法分类 递归过程又称为自调用过程。递归过程是利用栈的

4、技术来实现的。只不过这个过程是系统自动完成的。常见的递归方法有： 直接递归：就是函数或过程直接调用本身。如(a)所示。, 间接递归：一个函数或过程如果在调用其他函数或过程时，又产生了对自身的调用。如(b)图所示。, 尾递归：在一个递归过程或递归函数中递归调用语句是最后一条执行语句。,例6.2 以下是求 n!(n为正整数)的递归函数。 int fun(int n) int x; if (n=1) /*语句1*/ x=1; /*语句2*/ else /*语句3*/ x=fun(n-1)*n; /*语句4*/ return(x); /*语句5*/ 在该函数fun(n)求解过程中，直接调用fun(n-

5、1)(语句4)自身，所以它是一个直接递归函数。又由于递归调用是最后一条执行语句，所以它又属于尾递归。,6.1.2 递归调用的实现原理 - 栈与递归的实现(教材的6.2) 一、函数调用时的现场处理原则 1. 每调用一个函数，要将当前“现场信息”即当前参数、返回地址等压入栈顶， 2. 每当从一个函数退出时要将栈顶保存的最近一次的函数调用信息弹出即“恢复现场”， 3. 返回调用函数时,当前存储区保存的是调用时的现场内容。,二、现场处理的基本方法 1. 系统建立一个“递归工作栈”,作为整个递归函数运行期间使用的数据存储区; 2. 每进行一次调用便生成一个“工作记录”，其内容如下: 所有需要传递的参数、

6、所有局部变量、返回地址 并压入栈顶; 3. 退出一次递归时从栈顶弹出一个工作记录，按栈顶元素记录的返回地址继续执行;即利用栈实现现场保护与现场恢复。 如例6.2求 n!(n为正整数)递归函数执行过程中栈的变化记录：,int fun(int n) int x; if (n = =1) /*语句1*/ x=1; /*语句2*/ else /*语句3*/ x=fun(n-1)*n;/*语句4*/ return(x); /*语句5*/ ,栈中元素即现场保护工作记录的结构: (返回地址语句号, 传来的n) 假设n=5，返回地址为0表示程序结束。,开始执行 调用fun,(0,5),1,3,4 产生 递归,

7、(d4,4) 结束时返回fun(4)值*5(执行语句4),(d4,4),1,3,4,(d4,3) 结束时返回fun(3)值*4(执行语句4),(d4,3),1,3,4,(d4,2) 结束时返回fun(2)值*3(执行语句4),1,3,4,(d4,1) 结束时返回fun(1)值*2(执行语句4),结束递归,1,2,5,求得f(1)=1栈顶元素出栈恢复现场，并按记录执行语句4,4-5递归结束 已知f(1)=1,求得f(2)=f(1)*2弹出栈顶元素，即执行语句4,4-5递归结束 已知f(2)=2,求得f(3)=2*3弹出栈顶元素,4-5递归结束 已知f(3)=6,求得f(4)=6*4弹出栈顶元素,

8、4-5递归结束 已知(4)=24,求得f(5)=24*5 并执行语句0,分析下面程序： dunno(int m) 1 2 int value; 3 if (m=0) 4 value = 3; 5 else 6 value = dunno(m 1) + 5; 7 return(value); 8 9 执行语句 n=dunno(3) ,则n的值是多少？执行的语句序列是什么？,语句序列:,m=3,1 4，6，7，第一次递归，递归前m=3即执行n=dunno(2),m=2,1 4，6，7，第二次递归，递归前m=2即执行n=dunno(1),m=1,1 4，6，7，第三次递归，递归前m=1即执行n=du

9、nno(0),m=0,m=0,1 5，m=0,8 - 9: 结束第三次递归，返回3 执行语句7: 3+5后再执行8,9结束第二次递归,执行语句7: 8+5后再执行8,9结束第一次递归 执行语句7: 13+5后再执行8,9结束外界调用 对应的非递归程序：,int dunno(int m) int v=3,i; for(i=1;i%c”),i,a,c);,栈中元素即现场保护工作记录的结构:,(返回地址, 圆盘个数 n, 原在柱名 a, 临时柱名 b, 移到柱名 c),返回地址以语句编号表示, 塔的初始形式:,主函数调用时产生现场(0,3,a,b,c)进栈,0为主函调用后返回语句行号,0,3,a,b

10、,c,原状,1 2 4 5,当前现场(0,3,a,b,c)此次调用传来的参数,下一现场由move(n-1,a,c,b)产生为:,传来(第1参,第2参,第3参,第4参,第5参) 生成现场用(第2参-1,第3参,第5参,第4参),(6,2,a,c,b),6,2,a,c,b,原状,n=2,1 2 4 5,当前现场(6,2,a,c,b)即传来的参数 现场准备(6,n-1,a,c,b)=,(6,1,a,b,c) 现场(6,1,a,b,c)进栈,6,1,a,b,c,原状,n=1,1 2 3 9,当前现场(6,1,a,b,c)即传来的参数 执行3: movedisk(1,a,c)= 即1从a-c,1 2 i

11、f(n=1) 3 movedisk(1,a,c); 4 else 5 move(n-1,a,c,b); 6 movedisk(n,a,c); 7 move(n-1,b,a,c); 8 9 ,6 7,当前现场(6,2,a,c,b)即传来的参数 执行6: movedisk(n,a,c)= 即2从a-b,执行7:现场准备(n-1,b,a,c)=,(1,c,a,b) 现场(8,1,c,a,b)进栈,8,1,c,a,b,1 2 if(n=1) 3 movedisk(1,a,c); 4 else 5 move(n-1,a,c,b); 6 movedisk(n,a,c); 7 move(n-1,b,a,c)

12、; 8 9 ,1,2,3,9,当前现场(8,1,c,a,b) 执行3: movedisk(1,a,c)= 即1从c-b,执行9: 按栈顶指示转向行号8, 并弹出栈顶记录 恢复现场(6,2,a,c,b),8,9,当前现场(6,2,a,c,b) 执行9: 按栈顶指示转向行号6, 并弹出栈顶记录 恢复现场(0,3,a,b,c),不变,1 2 if(n=1) 3 movedisk(1,a,c); 4 else 5 move(n-1,a,c,b); 6 movedisk(n,a,c); 7 move(n-1,b,a,c); 8 9 ,6,7,当前现场(0,3,a,b,c) 执行6: movedisk(n

13、,a,c)=即3从a-c,执行7:现场准备(n-1,b,a,c)=(2,b,a,c) 现场(8,2,b,a,c)进栈,8,2,b,a,c,1,2,4,5,当前现场(8,2,b,a,c) 现场准备(n-1,a,c,b)=(1,b,c,a) 现场(6,1,b,c,a)进栈,不变,6,1,b,c,a,1 2 if(n=1) 3 movedisk(1,a,c); 4 else 5 move(n-1,a,c,b); 6 movedisk(n,a,c); 7 move(n-1,b,a,c); 8 9 ,1,2,3,9,当前现场(6,1,b,c,a) 执行3: movedisk(1,a,c)= 即1从b-a

14、,执行9: 按栈顶指示转向行号6, 并弹出栈顶记录 恢复现场(8,2,b,a,c),6,7,当前现场(8,2,b,a,c) 执行6: movedisk(n,a,c)=即2从b-c,执行7:现场准备(n-1,b,a,c)=(1,a,b,c) 现场(8,1,a,b,c)进栈,8,1,a,b,c,1,2,3,9,1 2 if(n=1) 3 movedisk(1,a,c); 4 else 5 move(n-1,a,c,b); 6 movedisk(n,a,c); 7 move(n-1,b,a,c); 8 9 ,当前现场(8,1,a,b,c) 执行3: movedisk(1,a,c)=即1从a-c,执行

15、9: 按栈顶指示转向行号8, 并弹出栈顶记录 恢复现场(8,2,b,a,c),8,9,当前现场(8,2,b,a,c) 执行9: 按栈顶指示转向行号0, 并弹出栈顶记录 恢复现场(0,3,a,b,c),不变,8,9,当前现场(0,3,a,b,c) 执行9: 按栈顶指示转向行号0, 并弹出栈顶记录 恢复现场: 空栈,同上,执行主函数调用语句的下一句,6.2 何时使用递归(教材的 6.1.2) 在以下三种情况下,常常要用到递归的方法。 1. 定义是递归的 有许多数学公式、数列等的定义是递归的。例如,求n!和Fibonacci数列等。这些问题的求解过程可以将其递归定义直接转化为对应的递归算法。,例6.

16、3 求Fibonacci数列的递归算法(即第一、第二个数为0和1，后面的每一个数都是其前两个数的和)，设计一个函数f(n)求的该数列： 规律是：先求f(n-1)、再求f(n-2)、这两个数求和得到第n个数x x=f(n-1)+f(n-2) 该数列的第一、第二个数为0和一，即 n=1(第一个数)时f(n)=0，n=2(第二个数)时f(n)=1 即递归体： x=f(n-1)+f(n-2) 出口：n=1或n=2时，f(n)=n-1,1 int Fib(int n) 2 3 int x; 4 if (n = = 1 | n = = 2) 5 x=n-1; 6 else 7 x=Fib(n-1)+Fib

17、(n-2); 8 ,假设n=5：求f(5)，,先求f(4),再求f(3),先求f(3),再求f(2),先求f(2),再求f(1),:f(2)=1返回,:f(1)=0返回,计算加法得f(3)=1返回,:f(2)=1返回,计算加法得f(4)=2返回,先求f(2),再求f(1),:f(2)=1返回,:f(1)=0返回,计算加法得f(3)=1返回,计算加法得f(5)=3返回,2. 数据结构是递归的 有些数据结构是递归的。例如，第2章中介绍过的单链表就是一种递归数据结构，其结点类型定义如下： typedef struct LNode ElemType data; struct LNode *next;

18、LinkList; 该定义中，结构体LNode的定义中用到了它自身，即指针域next是一种指向自身类型的指针，所以它是一种递归数据结构。,对于递归数据结构，采用递归的方法编写算法既方便又有效。例如，求一个不带头结点的单链表head的所有data域(假设为int型)之和的递归算法如下：,int Sum(LinkList *head) 1 2 if (head = = NULL) 3 return(head-data); 4 else 5 return(head-data+Sum(head-next); 6 7,假设链表如下：,栈的变化：,int Sum(LinkList *head) 1 2 i

19、f (head = = NULL) 3 return(head-data); 4 else 5 return(head-data+Sum(head-next); 6 7,初识状态,(0,表头指针),16 返回当前及下 一数据之和,(6, a1指针),(6, a2指针),(6, a3指针),(6, a4指针),14 执行6,返回a4,6-7 返回a3+a4,6-7 返回a2+a3+a4,6-7 返回a1+a2+a3+a4,6-7 返回a1+a2+a3+a4 0,3. 问题的求解方法是递归的 有些问题的解法是递归的，典型的有Hanoi问题求解，该问题描述是：设有3个分别命名为a,b和c的塔座，在塔

20、座a上有n个直径各不相同，从小到大依次编号为1,2,n的盘片，现要求将X塔座上的n个盘片移到塔座c上并仍按同样顺序叠放，盘片移动时必须遵守以下规则：每次只能移动一个盘片；盘片可以插在a,b和c中任一塔座；任何时候都不能将一个较大的盘片放在较小的盘片上。设计递归求解算法，并将其转换为非递归算法。, 借助 c 将 a 上的前 n-1 个移至 b : move(n-1,a,c,b) 即将 n-1 只盘从 a 经过 c 移至 b, 将第 n 个由 a 移至 c : movedisk(n,a,c), 借助 a 将 b 上的 n-1 个移至 c : move(n-1,b,a,c),其中、与原问题的特性完全

21、一致，只是盘的数量稍有不同。这样整体任务就划分成了两个子问题。而每个子问题的求解又可照章办理，各分解成两个 n-2 个盘的子问题，这样一直分解到只有一个盘的简单情形，问题就迎刃而解。然后再回溯，就可得到解决整体问题的完整步骤。编程就包括这三个函数,6.1.3 递归模型 递归模型是递归算法的抽象，它反映一个递归问题的递归结构。例如，前面的递归算法对应的递归模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 其中，第一个式子给出了递归的终止条件，第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系。我们把第一个式子称为递归出口，把第二个式子称为递归体

22、。,一般地，一个递归模型是由递归出口和递归体两部分组成，前者确定递归到何时结束，后者确定递归求解时的递推关系。 实际上，递归思路是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决(此时分解到递归出口)。但递归分解不是随意的分解，递归分解要保证“大问题”与“小问题”相似，即求解过程与环境都相似。一旦遇到递归出口，分解过程结束，开始求值过程，所以分解过程是“量变”过程，即原来的“大问题”在慢慢变小，但尚未解决。遇到递归出口后，便发生了“质变”，即原递归问题便转化成直接问题。,6.3

23、 递归算法的设计 递归求解过程的特征是：首先将整个问题划分为若干个子问题，通过分别求解子问题，最后获得整个问题的解。而这些子问题具有与原问题相同的求解方法，于是可以再将它们划分成若干个子问题，分别求解，如此反复进行，直到不能再划分成子问题，或已经可以求解为止。这种自上而下将问题分解、求解，再自上而下引用、合并，求出最后解答的过程称为递归求解过程。这是一种分而治之的算法设计方法。 递归算法设计先要给出递归模型，再转换成对应的C/C+语言函数。递归设计的步骤如下：,(1) 对原问题f(s)进行分析，假设出合理的“较小问题”f(s)(与数学归纳法中假设 n=k-1 时等式成立相似)； (2) 假设f

24、(s)是可解的，在此基础上确定f(s)的解，即给出f(s)与f(s)之间的关系(与数学归纳法中求证 n=k 时等式成立的过程相似)； (3) 确定一个特定情况(如f(1)或f(0)的解，由此作为递归出口(与数学归纳法中求证n=1时等式成立相似)。,例6.4 采用递归算法求斐波那契数列(Fibonacci number)：已知第一、第二个数为0和1，其他fib(n)的下一项为其前两项之和。,假设fib(n)为求解函数，并且假设fib(n-1)和fib(n)已求出，则： fib(n) = fib(n-1) + fib(n-2) 当n=1、n=2时，fib(0)=0、fib(1)=1，即 n2 时f

25、ib(n)=n-1，因此得到如下递归模型：,算法如下： int fib(int n) if(n Ai) return Ai; else return m; ,6.4 递归算法到非递归算法的转换 不是所有的高级程序设计语言都能提供递归功能，要提供递归功能，程序语言的编译器必须具有递归程序的能力。常见的计算机语言中，具备此条件的有C、Passcal、QBasic、Pl等。而在编译程序时必须决定所有相关信息的程序语言如FORTRAN、COBOL、BASIC等，还有一些低级语言都不能由递归概念编写程序。,1. 递归算法有两个基本特性： 一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方

26、法，对求解某些复杂问题，递归算法分析问题的方法是十分有效的； 二是一个递归算法在空间和时间上的需求都比非递归算法要高，也就是说，递归算法的时间效率通常比较差。因此，对求解某些问题时，我们希望用递归算法分析问题，用非递归算法具体求解问题。这就需要把递归算法转换为非递归算法。,2. 把递归算法转化为非递归算法有如下三种基本方法： (1) 对于尾递归和单向递归的算法，可用循环结构的算法替代。 (2) 自己用栈模拟系统的运行时的栈，通过分析只保存必须保存的信息，从而用非递归算法替代递归算法。 (3) 利用栈保存参数，由于栈的后进先出特性吻合递归算法的执行过程，因而可以用非递归算法替代递归算法。,本节讨

27、论第(1)种和第(2)种情况的递归算法转化为非递归算法的问题，前者是一种是直接转化法，不需要使用栈；后者是间接转化法，需要使用栈。第(3)种情况也需要使用栈，但因具体情况而异，例如，在教材第7章的例7.6就是这种情况的一个例子。,6.4.1 尾递归和单向递归的消除 尾递归是递归调用语句只有一个，而且是处于算法的最后。如阶乘算法： int fun(int n) int x; if (n=1) x=1; else x=fun(n-1)*n; return(x); /*递归方式求解*/ 就是尾递归。,尾递归的特点是：当递归调用返回时，返回到上一层递归调用的下一语句，而这个返回位置正好是算法的结尾。也就是说，以前每次递归调用时保存的返回地址、函数返回值和函数参数等实际上就不再使用了，这些信息没有必要保存。因此，对于尾递归形式的递归算法，