数据结构C递归课件.ppt

1、 优点：优点：采用采用编出的程序简洁、清晰，程序结编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。构符合结构化程序设计，可读性好。编译程序是如何处理这类带有递归调用功编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？语言，应该如何设计和实现这类程序呢？ 在定义自身的同时又出现了对自身的调用。在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调如果一个函数在其定义体内直接调用自己，则称直接递归函数。用自己，则称直接递归函数。如果一个函数经过一系列的中间如果一个函数

2、经过一系列的中间调用语句，通过其它函数间接调用自己，则称间调用语句，通过其它函数间接调用自己，则称间接递归函数接递归函数。 数学中常常利用递归手段来定义一些概念，数学中常常利用递归手段来定义一些概念，如求阶乘的运算。如求阶乘的运算。n的阶乘定义为：的阶乘定义为： n * ( n 1 ) ! n0 n! = 1 n=0例如例如: : 显然，该递归的出口是显然，该递归的出口是 0! =1。 long fac (int n) long p; if (n=0| n=1) p=1; else p=n*fac(n-1) ; return p; void main() long x=fac(5); cout

3、x; long fac (int n) long p; if (n=0 | n=1) p=1; else p=n*fac(n-1) ; return p; 递归函数包含：递归函数包含：1、递归调用语句递归调用语句，如，如 fac (n-1)；2、基值判断基值判断，如，如n=0 | n=1即为基值，保证了递归可以即为基值，保证了递归可以终止，满足基值条件后的计算终止，满足基值条件后的计算 p=1, 一般称为最终计算；一般称为最终计算；3、调用之后的返回处理调用之后的返回处理。如。如 p= n * fac (n-1) ，是返回之，是返回之后要进行的操作。后要进行的操作。fac(5)main()n=

4、5p=5*fac(4)第一层第一层facn=4p=4*fac(3)第二层第二层facn=3p=3*fac(2)第三层第三层facn=2p=2*fac(1)第四层第四层facn=1p=1第五层第五层facfac(2)=2fac(1)=1fac(3)=6fac(4)=24fac(5)=120输出输出假设调用该递归函数的假设调用该递归函数的主函数为主函数为第第0层层，则从主函数调，则从主函数调用递归函数为进入用递归函数为进入第第1层层；从第；从第 i层递归调用本身为进入层递归调用本身为进入“下一层下一层”，即，即第第 i+1 层层。反之，退出第。反之，退出第 i 层递归应返层递归应返回至回至“上一层

5、上一层”，即第，即第 i-1 层。层。递归层次递归层次: : 为了保证递归函数正确执行，系统需设立一个为了保证递归函数正确执行，系统需设立一个“递归递归工作栈工作栈”作为整个递归函数运行期间使用的数据存储区。作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个每一层递归所需信息构成一个“工作记录工作记录”，其中包括，其中包括所有的实参、所有的局部变量以及上一层的返回地址。所有的实参、所有的局部变量以及上一层的返回地址。 每进入一层递归，就产生一个新的工作记录每进入一层递归，就产生一个新的工作记录压入压入栈顶。栈顶。每退出一层递归就从栈顶每退出一层递归就从栈顶弹出弹出一个工作记录

6、，则当前执一个工作记录，则当前执行层的工作记录必须是递归工作栈栈顶的工作记录，称行层的工作记录必须是递归工作栈栈顶的工作记录，称这个记录为这个记录为“活动记录活动记录”，并称指示活动记录的栈顶指，并称指示活动记录的栈顶指针为针为“当前环境指针当前环境指针”。abc1号盘2号盘3号盘abc1号盘2号盘3号盘void Hanoi(int n, char x, char y, char z) if(n = = 1) move(x, 1, z); else Hanoi(n-1, x, z, y); move(x, n, z); Hanoi(n-1, y, x, z); 0123456789void m

7、ove (char x, int n, char y) cout移动移动n号盘子号盘子从柱子从柱子x到柱子到柱子y;Hanoi(n, x, y, z) 可以分成三个子问题：可以分成三个子问题：问题问题1.Hanoi(n-1, x, z, y) /将将X柱上的柱上的n-1个圆盘借助个圆盘借助Z柱移到柱移到Y柱上柱上，此时，此时X柱只剩下第柱只剩下第n个圆盘；个圆盘；问题问题2.Move( n, x， z) /将将X柱上的第柱上的第n个移动到个移动到Z柱柱问题问题3.Hanoi(n-1, y, x, z) /将将Y柱上的柱上的n-1个圆盘借助个圆盘借助X柱移到柱移到Z柱上柱上；n=1时可以直接求解

8、时可以直接求解void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); elseelse Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,4,51递归递归

9、层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); elseelse Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y

10、, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,4,52递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-

11、1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,3,93递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b6,1,a,b,c盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char

12、y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc6,72递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号123voi

13、d Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1)if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,3,93递归递归层次层次运行语运行语

14、句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b8,1,c,a,b盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Han

15、oi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc8,92递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Han

16、oi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc6,71递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n =

17、 = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); elseelse Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,4,52递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态8,2,b,a,c盘号盘号123void Hanoi(int n,

18、 char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1)if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,3,93递归递归层次层次运行语运行语句序号句序号递归工作栈状态递

19、归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态8,2,b,a,c8,1,b,c,a盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x,

20、z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc6,72递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态8,2,b,a,c盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z,

21、y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc1,2,3,93递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态8,2,b,a,c8,1,a,b,c盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z

22、) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc8,92递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态8,2,b,a,c盘号盘号123void Hanoi(i

23、nt n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y, x, z); 0123456789 0,3,a,b,cabc8,91递归递归层次层次运行语运行语句序号句序号递归工作栈状

24、态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号123void Hanoi(int n, char x, char y, char z) void Hanoi(int n, char x, char y, char z) if(n = = 1) if(n = = 1) move(x, 1, z); move(x, 1, z); else else Hanoi(n-1, x, z, y); Hanoi(n-1, x, z, y);move(x, n, z);move(x, n, z); Hanoi(n-1, y, x, z);Hanoi(n-1, y,

25、 x, z); 0123456789 栈空栈空abc0递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号123 选择递归选择递归 还是还是 非递归：非递归： 采用递归方式实现问题的算法程序具有采用递归方式实现问题的算法程序具有结构清晰、结构清晰、读性好、易于理解等优点读性好、易于理解等优点，但递归程序较之非递归程，但递归程序较之非递归程序无论是空间需求还是时间需求都更高，因此在希望序无论是空间需求还是时间需求都更高，因此在希望节省存储空间和追求执行效率节省存储空间和追求执行效率的情况下，人们更希望的情

26、况下，人们更希望使用非递归方式实现问题的算法程序。使用非递归方式实现问题的算法程序。 （1 1）在求解过程中直接）在求解过程中直接求值，无需回溯。称这求值，无需回溯。称这类递归问题为类递归问题为简单递归简单递归问题问题；（2 2）另一类递归问题在）另一类递归问题在求解过程中不能直接求求解过程中不能直接求值，必须进行试探和回值，必须进行试探和回溯，称这类递归问题为溯，称这类递归问题为复杂递归问题复杂递归问题。转换方法不同：转换方法不同：（1 1）简单递归问题可）简单递归问题可以采用以采用递推递推方法直接方法直接求解；求解；（2 2）复杂递归问题由）复杂递归问题由于要进行于要进行回溯回溯，在实，在

27、实现过程中必须现过程中必须借助栈借助栈来管理和记忆来管理和记忆回溯点回溯点。 将原问题将原问题分解分解成若干结构与原问题相同，但规模较小成若干结构与原问题相同，但规模较小的子问题，并建立原问题与子问题解之间的的子问题，并建立原问题与子问题解之间的递推关系递推关系，然后定义若干变量用于记录递推关系的每个子问题的然后定义若干变量用于记录递推关系的每个子问题的解；解； 程序的执行便是根据递推关系，不断修改这些变量的程序的执行便是根据递推关系，不断修改这些变量的值，使之成为更大子问题的解的过程；当得到原问题值，使之成为更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。解时，递推过程便可结束了

28、。 int Fact ( int n ) int i , fac; fac=1; /*将变量将变量fac初始化为初始化为Fact(0)的值的值*/ for (i=1;i1float p(int n, float x) float p1, p2; if (n=0) return(1.0); /终止条件终止条件 else if (n=1) return(x); /终止条件终止条件 else p1=(2*n-1)*x*p(n-1,x); p2=(n-1)*p(n-2,x); return(p1-p2)/n); 如果仍然采用如果仍然采用p(n,x)表示第表示第n阶勒让德多项式的值，则在阶勒让德多项式的

29、值，则在i1的情况下的情况下有如下递推关系成立有如下递推关系成立： p(i,x)=(2i-1) x p(i-1,x) (i-1) p(i-2,x)/i 显然，可以利用以上递推关系，从显然，可以利用以上递推关系，从i=2开始，逐步增大开始，逐步增大i的的值，依次求解第值，依次求解第i阶勒让德多项式的值；当阶勒让德多项式的值；当i=n时，便求到了时，便求到了p(n,x)的值。在整个求解过程中不需要进行试探和回溯，因的值。在整个求解过程中不需要进行试探和回溯，因而该问题而该问题属于属于简单递归简单递归问题问题，完全可以使用递推技术加以实，完全可以使用递推技术加以实现。现。 定义两个变量定义两个变量p

30、re1和和pre2，分别记录上述递推关系中两，分别记录上述递推关系中两个子问题的解，即个子问题的解，即pre1=p(i-2,x)，pre2=p(i-1,x)，且且pre1和和pre2的值始终随着的值始终随着i的值的改变而发生变化：每的值的改变而发生变化：每当新求出第当新求出第i阶多项式的值后，阶多项式的值后，i的值要增加的值要增加1，而在此之，而在此之前应该前应该修改修改pre1和和pre2的值，用的值，用pre1记录记录pre2当前当前的值，的值，而用而用pre2记录记录新求出新求出的多项式的值，直至的多项式的值，直至i=n。 float p ( int n, float x ) float

31、 pre1,pre2,a,b,valuep; int i; if (n=0) return(1.0); else if (n=1) return(x); else pre1=1.0; pre2=x; for (i=2;i=n;+i) a=2*i-1; b=i-1; valuep=(a*pre2*x-b*pre1)/i; pre1=pre2; pre2=valuep; return(valuep); 复杂递归问题在求解的过程中无法保证求解复杂递归问题在求解的过程中无法保证求解动作一直向前，动作一直向前，往往需要设置一些回溯点往往需要设置一些回溯点，当求解无法进行下去或当前处理的工作已经当求解无法

32、进行下去或当前处理的工作已经完成时，必须退回到所设置的回溯点，继续完成时，必须退回到所设置的回溯点，继续问题的求解。因此，在使用非递归方式实现问题的求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，经常使用一个复杂递归问题的算法时，经常使用栈栈来来记录和管理所设置的回溯点。记录和管理所设置的回溯点。 按中点优先的顺序遍历线性表问题：按中点优先的顺序遍历线性表问题： 已知线性表已知线性表list以顺序存储方式存储，要求按以顺序存储方式存储，要求按以下顺序输出以下顺序输出list中所有结点的值：首先输出中所有结点的值：首先输出线性表线性表list中点位置上的元素值，然后输出中中点位置上的元

33、素值，然后输出中点左部所有元素的值，再输出中点右部所有元点左部所有元素的值，再输出中点右部所有元素的值；而无论输出中点左部所有元素的值还素的值；而无论输出中点左部所有元素的值还是输出中点右部所有元素的值，也均应遵循以是输出中点右部所有元素的值，也均应遵循以上规律。上规律。例如，例如，已知数组已知数组list中元素的值为：中元素的值为： 18 32 04 09 26 06 10 30 12 08 45则则list中元素按中点优先顺序遍历的输出结果为：中元素按中点优先顺序遍历的输出结果为： 06 04 18 32 09 26 12 10 30 08 45试采用递归和非递归算法实现该遍历问题。试采用

34、递归和非递归算法实现该遍历问题。#define MAXSIZE 20typedef int listarrMAXSIZE;void listorder(listarr list, int left, int right) int mid; if (left=right) mid=(left+right)/2; coutlistmid“ ”; listorder(list,left,mid-1); listorder(list,mid+1,right); #define MAXSIZE 20typedef int listarrMAXSIZE;void listorder(listarr lis

35、t, int left, int right) typedef struct int l; /*存放待处理数组段的起点下标存放待处理数组段的起点下标*/ int r; /*存放待处理数组段的终点下标存放待处理数组段的终点下标*/ stacknode; /*栈中每个元素的类型栈中每个元素的类型*/ stacknode stackMAXSIZE; int top, i, j, mid; /*top为栈顶指针为栈顶指针*/ if (left=right) /*数组段不为空数组段不为空*/ top= -1; i=left; j=right; while (i=j | top!=-1) /*当前正在处理的数组段非空或栈非空当前正在处理的数组段非空或栈非空*/ if (i=j) mid=(i+j)/2; coutlistmid“ ”; +top; stacktop.l=mid+1; stacktop.r=j; j=mid-1; else /*当前正在处理的数组段为空时进行回溯当前正在处理的数组段为空时进行回溯*/ i=stacktop.l; j=stacktop.r; top - - ;