合工大数据结构 06-递归

1、1数数 据据 结结 构构（第六章第六章 递归递归） Data Structures张晶张晶计算机与信息学院计算机与信息学院 2022-5-132022-5-132第六章第六章 递归递归 （Recursive） 6.1 递归的定义递归的定义 6.2 递归的内部实现原理递归的内部实现原理 6.3 递归程序的阅读递归程序的阅读 6.4 递归程序的正确性证明递归程序的正确性证明 6.5 递归程序的模拟递归程序的模拟转换为非递归转换为非递归 3第六章第六章 递归递归6.1 递归的定义递归的定义 (1) 作为一种作为一种程序形式程序形式的的递归递归： 在函数的执行过程中调用自身。在函数的执行过程中调用自身

2、。 可能有两种形式：可能有两种形式： 直接递归直接递归-在函数体内调用自身，在函数体内调用自身， 间接递归间接递归-函数中调用其他函数，并由其他函数调用自身函数中调用其他函数，并由其他函数调用自身 (2) 更是作为一种更是作为一种程序设计（算法设计）的技术程序设计（算法设计）的技术的递归。的递归。 因为一些问题的求解具有这样的特点：因为一些问题的求解具有这样的特点： 原问题可以分解为若干子问题分别进行求解，适当地合并子原问题可以分解为若干子问题分别进行求解，适当地合并子问题的解可以得到原问题的解。问题的解可以得到原问题的解。 而子问题的求解方式与原问题的求解相同，而子问题的求解方式与原问题的求

3、解相同， 因而需要调用相同的函数来实现，因而需要调用相同的函数来实现， 由此而涉及到递归技术。由此而涉及到递归技术。46.1 递归的定义递归的定义例例6.1 阶乘阶乘n!的定义如下：的定义如下： 1 当当n=0时时 n!= n(n-1)! 当当n0时时对应的求阶乘的对应的求阶乘的递归函数递归函数如下：如下： int fact（int n） if ( n = 0 ) return 1; else return n * fact( n 1 ); 函数fact的函数体内调用自身， 即fact( n 1 ); 56.1 递归的定义递归的定义例例 6.2 下面是一个递归函数下面是一个递归函数fn的定义的

4、定义-斐波诺契函数：斐波诺契函数： f1=1 f2=2 fn = fn-1 + fn-2 n2例例6.3 下面是一个对链表执行操作的函数，请判断其功能。下面是一个对链表执行操作的函数，请判断其功能。 void print( node * L ) if ( L != NULL ) cout data; print( L - next ); void list:print()node *p=head-next;while(p!=NULL) coutdata; p=p-next; 66.1 递归的定义o 递归函数的一般形式：递归函数的一般形式： void Pname( 参数表参数表 ) if ( 条

5、件条件 ) 简单操作简单操作; else 简单操作简单操作; Pname (实参表实参表); 简单操作简单操作; Pname (实参表实参表); 简单操作简单操作; 递归出口递归出口可能有多次的调用可能有多次的调用例如：在阶乘函数例如：在阶乘函数int fact（int n） if ( n = 0 ) return 1; else return n * fact( n 1 ); 递归出口是递归出口是n=0函数也可以是其他类型；函数也可以是其他类型；调用方式自然也不同调用方式自然也不同76.2 递归的内部实现原理o 6.2.1 一般函数的内部实现一般函数的内部实现 程序程序A:a1;B;a2;B

6、;a3;B;a4;程序程序A:a1;B;a2;B;a3;B;a4;子程序BCall BCall BCall B86.2 递归的内部实现原理（1）从程序的）从程序的执行过程执行过程来讨论来讨论: 在在执行调用执行调用时时, 计算机内部计算机内部至少执行至少执行如下操作如下操作: （a） 保存返回地址保存返回地址, 也就是将返回地址入栈。也就是将返回地址入栈。 （b） 为被调子程序为被调子程序准备数据准备数据: 计算实在参数的值计算实在参数的值, 并赋给对应的形参。并赋给对应的形参。 （c） 转入子程序转入子程序执行。执行。 在在执行返回执行返回操作时操作时, 计算机内部至少执行如下操作计算机内部

7、至少执行如下操作: （a） 从栈顶从栈顶取取出出返回地址返回地址，并出栈。，并出栈。 （b） 按返回地址按返回地址返回返回。96.2递归的内部实现原理（2）关于）关于局部变量局部变量的实现的讨论的实现的讨论 在在执行调用时执行调用时, 内部操作如下内部操作如下: （a） 保存返回地址保存返回地址入栈，入栈， 同时在栈顶为被调函数的局部变量和形参开辟存储空间。同时在栈顶为被调函数的局部变量和形参开辟存储空间。 （b）为被调子程序）为被调子程序准备数据准备数据: 计算实在参数的值计算实在参数的值, 并赋给对应的形参（并赋给对应的形参（在栈顶在栈顶）。）。 （c） 转入子程序转入子程序执行。执行。

8、在在执行返回执行返回操作时操作时, 计算机内部至少执行如下操作计算机内部至少执行如下操作: （a）从栈顶）从栈顶取出返回地址取出返回地址，并出栈，并出栈 （同时撤消了被调函数的局部变量和形参）。（同时撤消了被调函数的局部变量和形参）。 （b）按返回地址）按返回地址返回。返回。106.2递归的内部实现原理（3）关于返回值的实现的讨论）关于返回值的实现的讨论 返回操作返回操作的内部实现的内部实现修改修改为如下几项为如下几项: （a）若函数需要返回值，将其值保存到回传变量中若函数需要返回值，将其值保存到回传变量中。 （b）从栈顶取出返回地址，并退栈。）从栈顶取出返回地址，并退栈。 （c）按返回地址返

9、回。）按返回地址返回。 （d）在返回后自动执行以下操作：在返回后自动执行以下操作： 若函数需要返回值，从回传变量中取出所保存的若函数需要返回值，从回传变量中取出所保存的值，并传送到相应的变量或位置上。值，并传送到相应的变量或位置上。116.2递归的内部实现原理o 6.2.2递归调用的内部实现原理递归调用的内部实现原理 可将递归调用可将递归调用理解为理解为: 调用与自己有相同的代码和同名的局部变量的子程序。调用与自己有相同的代码和同名的局部变量的子程序。由此可知：由此可知： 执行执行递归调用递归调用及及返回返回的内部实现的内部实现与前述实现相同与前述实现相同: 在执行在执行递归调用递归调用时时,

10、 计算机内部执行如下操作计算机内部执行如下操作: (a) 开辟栈顶存储空间，用于保存：开辟栈顶存储空间，用于保存： 返回地址、被调层（函数）中的形参和局部变量的值。返回地址、被调层（函数）中的形参和局部变量的值。 (b)为被调层（函数）准备数据：计算实参的值为被调层（函数）准备数据：计算实参的值, 并赋给对并赋给对应的形参（在栈顶元素中）。应的形参（在栈顶元素中）。 (c) 转入子程序执行。转入子程序执行。 126.2递归的内部实现原理在在执行返回执行返回操作时操作时, 内部实现如下内部实现如下:（a）若函数需要返回值，将其值保存到回传变量中。）若函数需要返回值，将其值保存到回传变量中。（b）

11、从栈顶取出返回地址，并退栈）从栈顶取出返回地址，并退栈 -同时撤消被调层子程序的局部变量及形参。同时撤消被调层子程序的局部变量及形参。（c）按返回地址返回。）按返回地址返回。（d）在返回后自动执行如下操作：）在返回后自动执行如下操作： 若函数需要返回值，从回传变量中取出若函数需要返回值，从回传变量中取出 所保存的所保存的值值,并传送到相应的实变参或位置上。并传送到相应的实变参或位置上。136.2 递归的内部实现原理例：根据递归程序的内部实现过程求解例：根据递归程序的内部实现过程求解return hcf(28,6)的执行结果。的执行结果。 int hcf(int M, int N) (1) if

12、 ( N=0)(2) cout0) cout 0) cout n; p(n-1); cout 0) p(n-1); cout n; p(n-1); 176.3 递归程序的阅读o例例：函数F定义如下, 用上述方法求出F(6)的值。 int F(int N) if ( N=2) return 1; return (2*F(N-1)+3*F(N-2); 解解: F(6)2*F(5)3*F(4)2*F(4) + 3*F(3)2*F(3) + 3*F(2)2*F(3)+3*F(2)2*F(2)+3*F(1)2*F(2)+3*F(1)2*F(2)+3*F(1)+11115111551131341121最终

13、解为12118递归样例-1o /求数组和求数组和o #includeo using namespace std;o long sum(int a, int n)o oif(n=1) return a0;oelseoreturn an-1+sum(a,n-1);o 19递归样例-2o1o2 2o3 3 3o4 4 4 4o5 5 5 5 5o#includeousing namespace std;ovoid print(int n)ooif(n=0)oreturn ;oelseooprint(n-1);ofor(int i=0;in;+i)ocoutn ;ocoutendl;oo20递归样例-

14、3o杨辉三角o#include #include oint Y(int i, int n)/递归求第n行第i个元素的值 if(i = 1 | i = n)return 1; else return Y(i,n-1)+Y(i-1,n-1);void YangHui(int n) int x,y; for(y = 1; y = n; y+) for(x = 1; x = y; x+) printf(%3d ,Y(x,y); printf(n); 21递归样例-4o梵塔问题：有梵塔问题：有 n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在个半径各不相同的圆盘，按半径从大到小，自下而上依次套在

15、 A柱上，另外还有柱上，另外还有 B、 C两根空柱。要求将两根空柱。要求将 A柱上的柱上的 n个圆盘全部搬到个圆盘全部搬到 C柱上去，每次只能搬动一个盘子，且必须始终保持柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。每根柱子上是小盘在上，大盘在下。 在移动盘子的过程当中发现要搬动在移动盘子的过程当中发现要搬动 n个盘子，必须先将个盘子，必须先将 n-1个盘个盘子从子从 A柱搬到柱搬到 B柱去再将柱去再将 A柱上的最后一个盘子搬到柱上的最后一个盘子搬到 C柱，最后从柱，最后从 B柱上将柱上将 n-1个盘子搬到个盘子搬到 C柱去。柱去。搬动搬动 n个盘子和搬动个盘子和

16、搬动 n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。o程序如下程序如下:o/hanio问题问题o#includeousing namespace std;o/original为开始的柱子为开始的柱子,temp为中转用的柱子为中转用的柱子o/destination为目的地的柱子为目的地的柱子ovoid hanio(int n,char original,char temp,char destination)ooif(n=1)ocoutMove disk n from ooriginal to destinationendl;

17、oelseoohanio(n-1,original,destination,temp);ocoutMove disk n from ooriginal to destination0时时 fact(n)函数如下：函数如下： int fact（int n） if ( n = 0 ) return 1; else return n * fact( n 1 ); 证明：证明： (1) 当当n=0时，调用函数得到值为时，调用函数得到值为1，符合函数定义，功能正确。，符合函数定义，功能正确。 (2) 假设假设0nk时，函数正确，即函数时，函数正确，即函数fact(n)的结果为的结果为n(n-1)! ，

18、则当则当n = k 0时，时， 由程序可知由程序可知 fact(n)=n*fact(n-1)=n* (n-1) (n-2)! = n* (n-1)!，功能正确。，功能正确。 综上所述，程序功能正确。综上所述，程序功能正确。236.4 递归程序的正确性证明o例例：对右面的函数，证明：对右面的函数，证明：（）调用（）调用P(n)所产生的输出项数为所产生的输出项数为2n-1。(n0)（）调用（）调用P(n)所产生的输出项中的奇数项为所产生的输出项中的奇数项为1。(n0)证明（）：证明（）： (1) 当当n=0时时, 由程序描述可知由程序描述可知, 不产生输出不产生输出, 即项数为即项数为0，符合命题

19、。，符合命题。 (2) 设设0nk时，命题正确，即调用时，命题正确，即调用P(n)产生产生2n-1项输出，项输出， 则当则当nk时，时， 由程序描述可知，要依次执行如下操作：由程序描述可知，要依次执行如下操作： P(n-1); cout0) P(n-1); coutn; P(n-1); 246.4 递归程序的正确性证明o 练习：练习：（）（）证明证明print(L)能输出链表能输出链表L中所有结点值。中所有结点值。 void print( link L ) if ( L != NULL ) cout data; print( L - next ); （）（）证明证明print(L)能按反序输出

20、链表能按反序输出链表L中所有结点值。中所有结点值。 void print( link L ) if ( L != NULL ) print( L - next ); cout data; 256.5 递归程序的模拟转换为非递归 o 背景：背景：为何要将递归程序转换为等价的非递归程序？为何要将递归程序转换为等价的非递归程序？n递归程序虽然有良好的可读性，但由于以下一些原因，需要将递递归程序虽然有良好的可读性，但由于以下一些原因，需要将递归程序转化为等价的非递归程序：归程序转化为等价的非递归程序：o 时间花费时间花费o 空间开销空间开销o 一部分编程环境的不支持，或者编写起来复杂。一部分编程环境的

21、不支持，或者编写起来复杂。o 如何转换？如何转换？n一种方式是重新设计一种方式是重新设计 没有利用已有的工作基础没有利用已有的工作基础n还有一种方式是对给定的递归程序，用一组规则进行等价的转换。还有一种方式是对给定的递归程序，用一组规则进行等价的转换。 问题是，规则包括哪些？问题是，规则包括哪些？266.5 递归程序的模拟o 机械地机械地将任何一个递归程序转换为与其等价的非递归程序将任何一个递归程序转换为与其等价的非递归程序o 五条规则：五条规则： (1) 设置一个栈（不妨用表示），并且开始时将其置为空。设置一个栈（不妨用表示），并且开始时将其置为空。 (2) 在子程序入口处设置一个标号（不妨

22、设为在子程序入口处设置一个标号（不妨设为L0）。）。 (3) 对子程序中的每一递归调用，用以下几个等价操作来替换：对子程序中的每一递归调用，用以下几个等价操作来替换： （a）保留现场：开辟栈顶存储空间，用于保存返回地址（不妨用）保留现场：开辟栈顶存储空间，用于保存返回地址（不妨用 Li，i=1,2,3，）、调用层中的形参和局部变量的值（最外层调）、调用层中的形参和局部变量的值（最外层调用不必考虑）。用不必考虑）。 （b）准备数据：为被调子程序准备数据，即计算实在参数的值）准备数据：为被调子程序准备数据，即计算实在参数的值, 并赋给对应的形参并赋给对应的形参 （c）转入（子程序）执行）转入（子程

23、序）执行, 即执行即执行goto L0。 （d）在返回处设一个标号）在返回处设一个标号Li(i=1,2,3，)，并根据需要设置以下，并根据需要设置以下语句：若函数需要返回值，从回传变量中取出所保存的值并传语句：若函数需要返回值，从回传变量中取出所保存的值并传 送到相应的位置。送到相应的位置。程序程序B：a1;B;a2;B;a3;B;a4;Call BCall BCall B276.5 递归程序的模拟转换为非递归 (4) 对返回语句，可用以下几个等价操作来替换：对返回语句，可用以下几个等价操作来替换： 如果栈不空，则依次执行如下操作，否则结束本子程序，返回。如果栈不空，则依次执行如下操作，否则结

24、束本子程序，返回。 （a）回传数据：若函数需要返回值，将其值保存到回传变量中。）回传数据：若函数需要返回值，将其值保存到回传变量中。 （b）恢复现场：从栈顶取出返回地址（不妨保存到中）及各）恢复现场：从栈顶取出返回地址（不妨保存到中）及各 变量、形参值，并退栈。变量、形参值，并退栈。 （c）返回：按返回地址返回（即执行）返回：按返回地址返回（即执行goto ）。）。 (5) 对其中的非递归调用和返回操作可照搬。对其中的非递归调用和返回操作可照搬。o例：将下面递归程序转换为等价的非递归程序。例：将下面递归程序转换为等价的非递归程序。 void P(int n) if ( n 0 ) P( n 1

25、 ); cout 0) cout0)cout0) s.push( n, L1); n = n - 1; goto L0; L1: cout0) s.push( n); n = n - 1; goto L0; L1: cout0s.push(n);n=n-1; s.empty( )? s.pop (n ); L1: cout 0 ) s.push ( n ); n = n - 1; while ( !s.empty( ) ) s.pop ( n ); cout 0s.push(n);n=n-1; s.empty( )? s.pop (n ); L1: cout 0 ) cout 0 ) / 规则

26、规则5 cout0 ) cout0cout 0 ) cout 0cout 0 ) / 规则5 cout 0 ) cout 0cout 0 ) cout 0 ) coutn; s.push (n); n=n-1; goto L0; L1: n=n-1; goto L0; L2: if (!s.empty( ) ) s.pop (n); goto L1; 396.6 递归技术的应用举例o 求集合1,2,N的幂集。o 设计算法求n个元素的全排列。40课后练习写出下面程序或调用的结果:(1) void P1(int W) int A,B; A=W-1; B=W+1; coutAB; void P2(W int ) int A,B;A=2*W;