数据结构C递归课件

《数据结构C递归课件》由会员分享，可在线阅读，更多相关《数据结构C递归课件（43页珍藏版）》请在装配图网上搜索。

1、一、递归一、递归递归是程序设计中最有力的方法之一。递归是程序设计中最有力的方法之一。递归是程序设计中最有力的方法之一。递归是程序设计中最有力的方法之一。优点：优点：采用采用递归递归递归递归编出的程序简洁、清晰，程序结编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。构符合结构化程序设计，可读性好。问题：问题：问题：问题：编译程序是如何处理这类带有递归调用功编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？语言，应该如何设计和实现这类程序呢？1 1一、递归一、递归递归递归递归递归:

2、在定义自身的同时又出现了对自身的调用。在定义自身的同时又出现了对自身的调用。直接递归函数直接递归函数直接递归函数直接递归函数:如果一个函数在其定义体内直接调如果一个函数在其定义体内直接调用自己，则称直接递归函数。用自己，则称直接递归函数。间接递归函数：间接递归函数：间接递归函数：间接递归函数：如果一个函数经过一系列的中间如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间调用语句，通过其它函数间接调用自己，则称间接递归函数接递归函数。2 2数学中常常利用递归手段来定义一些概念，数学中常常利用递归手段来定义一些概念，如求阶乘的运算。如求阶乘的运算。n的阶乘定义为：的阶乘定义为：

3、n*(n1)!n0n!=1n=0例如例如:显然，该递归的出口是显然，该递归的出口是0!=1。3 3求阶乘的算法如下：求阶乘的算法如下：求阶乘的算法如下：求阶乘的算法如下：longfac(intn)longp;if(n=0|n=1)p=1;elsep=n*fac(n-1);returnp;voidmain()longx=fac(5);cout0n0的一般情况可采用如下分治策略进行移动的一般情况可采用如下分治策略进行移动的一般情况可采用如下分治策略进行移动的一般情况可采用如下分治策略进行移动 （1 1）将）将）将）将1 1至至至至n-1n-1号盘从号盘从号盘从号盘从 a a 轴移动至轴移动至轴移动

4、至轴移动至 b b 轴，可递归求解轴，可递归求解轴，可递归求解轴，可递归求解Hanoi(n-1,a,c,b)Hanoi(n-1,a,c,b)；（2 2）将）将）将）将 n n号盘从号盘从号盘从号盘从 a a 轴移动至轴移动至轴移动至轴移动至 c c 轴；轴；轴；轴；（3 3）将）将）将）将1 1至至至至n-1n-1号盘从号盘从号盘从号盘从b b轴移动至轴移动至轴移动至轴移动至c c轴，可递归求解轴，可递归求解轴，可递归求解轴，可递归求解 Hanoi(n-1,b,a,c)Hanoi(n-1,b,a,c)。1010例：例：例：例：分析分析分析分析HanoiHanoi塔问题移动圆盘的次数塔问题移动圆

5、盘的次数塔问题移动圆盘的次数塔问题移动圆盘的次数 设设设设T(n)T(n)表示表示表示表示n n个圆盘的个圆盘的个圆盘的个圆盘的HanoiHanoi塔问题移动圆盘的次数，塔问题移动圆盘的次数，塔问题移动圆盘的次数，塔问题移动圆盘的次数，显然显然显然显然T(0)=0T(0)=0，对于，对于，对于，对于n0n0的一般情况采用如下分治策略：的一般情况采用如下分治策略：的一般情况采用如下分治策略：的一般情况采用如下分治策略：（1 1）将）将）将）将1 1至至至至n-1n-1号盘从号盘从号盘从号盘从 a a 轴移动至轴移动至轴移动至轴移动至 b b 轴，可递归求解轴，可递归求解轴，可递归求解轴，可递归求

6、解Hanoi(n-1,a,c,b)Hanoi(n-1,a,c,b)；（2 2）将）将）将）将 n n号盘从号盘从号盘从号盘从 a a 轴移动至轴移动至轴移动至轴移动至 c c 轴；轴；轴；轴；（3 3）将）将）将）将1 1至至至至n-1n-1号盘从号盘从号盘从号盘从b b轴移动至轴移动至轴移动至轴移动至c c轴，可递归求解轴，可递归求解轴，可递归求解轴，可递归求解 Hanoi(n-1,b,a,c)Hanoi(n-1,b,a,c)。在（在（在（在（1 1）与（）与（）与（）与（3 3）中需要移动圆盘次数）中需要移动圆盘次数）中需要移动圆盘次数）中需要移动圆盘次数T(n-1)T(n-1)，（，（，

7、（，（2 2）需要移动一次圆盘。可得如下的关系：需要移动一次圆盘。可得如下的关系：需要移动一次圆盘。可得如下的关系：需要移动一次圆盘。可得如下的关系：T(n)=2T(n-1)+1T(n)=2T(n-1)+1展开上式可得：展开上式可得：展开上式可得：展开上式可得：T(n)T(n)=2T(n-1)+1=2T(n-1)+1=22T(n-2)+1+1=22T(n-2)+1+1=2=22 2T(n-2)+1+2T(n-2)+1+2=2=2n nT(n-n)+1+2+2T(n-n)+1+2+2n-1n-1=2=2n n-1-11111二、二、汉诺塔问题的递归算法汉诺塔问题的递归算法voidHanoi(in

8、tn,charx,chary,charz)if(n=1)move(x,1,z);elseHanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);0123456789voidmove(charx,intn,chary)cout移动移动n号盘子号盘子从柱子从柱子x到柱子到柱子y;1212Hanoi(n,x,y,z)可以分成三个子问题：可以分成三个子问题：问题问题1.Hanoi(n-1,x,z,y)/将将X柱上的柱上的n-1个圆盘借助个圆盘借助Z柱移到柱移到Y柱上，柱上，此时此时X柱只剩下第柱只剩下第n个圆盘；个圆盘；问题问题2.Move(n,x，z)/将将X柱上

9、的第柱上的第n个移动到个移动到Z柱柱问题问题3.Hanoi(n-1,y,x,z)/将将Y柱上的柱上的n-1个圆盘借助个圆盘借助X柱移到柱移到Z柱上；柱上；n=1时可以直接求解时可以直接求解1313void 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);Hano

10、i(n-1,y,x,z);0123456789 0,3,a,b,cabc1,2,4,51递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号1231414void 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

11、,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）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号1231515void 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);Ha

12、noi(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盘号盘号1231616void 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,

13、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盘号盘号1231717void Hanoi(int n,char x,char y,char z)void Hanoi(int n,char x,char y

14、,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递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b8,1,c,a,b盘号盘号1231818void Hanoi(int n,char x,

15、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,92递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态6,2,a,c,b盘号盘号

16、1231919void 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,cabc6,71递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,

17、y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号1232020void 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,52递归递归层次层次运行语运行语句序号句序号递归工作栈

18、状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态8,2,b,a,c盘号盘号1232121void 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,ca

19、bc1,2,3,93递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态8,2,b,a,c8,1,b,c,a盘号盘号1232222void 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

20、,x,z);Hanoi(n-1,y,x,z);0123456789 0,3,a,b,cabc6,72递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态8,2,b,a,c盘号盘号1232323void 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

21、(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盘号盘号1232424void 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

22、 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盘号盘号1232525void Hanoi(int n,char x,char y,char z)void Hanoi(int n,char x,char y,char z)if(n=1)if(n

23、=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递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号1232626void Hanoi(int n,char x,char y,char z)void Hanoi(int n,char x,cha

24、r 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 栈空栈空abc0递归递归层次层次运行语运行语句序号句序号递归工作栈状态递归工作栈状态（返址，盘号，（返址，盘号，x,y,z）塔与圆盘的状态塔与圆盘的状态盘号盘号1232727三、递归程序到非递归程序的转换三、递归程序到非递归程序的转换选择递归选择递归 还是还是 非递归：非递归

25、：采用递归方式实现问题的算法程序具有采用递归方式实现问题的算法程序具有结构清晰、结构清晰、读性好、易于理解等优点读性好、易于理解等优点，但递归程序较之非递归程，但递归程序较之非递归程序无论是空间需求还是时间需求都更高，因此在希望序无论是空间需求还是时间需求都更高，因此在希望节省存储空间和追求执行效率节省存储空间和追求执行效率的情况下，人们更希望的情况下，人们更希望使用非递归方式实现问题的算法程序。使用非递归方式实现问题的算法程序。2828求解递归问题的两种方式求解递归问题的两种方式（1 1）在求解过程中直接）在求解过程中直接求值，无需回溯。称这求值，无需回溯。称这类递归问题为类递归问题为简单递

26、归简单递归问题问题；（2 2）另一类递归问题在）另一类递归问题在求解过程中不能直接求求解过程中不能直接求值，必须进行试探和回值，必须进行试探和回溯，称这类递归问题为溯，称这类递归问题为复杂递归问题复杂递归问题。转换方法不同：转换方法不同：（1 1）简单递归问题可）简单递归问题可以采用以采用递推递推方法直接方法直接求解；求解；（2 2）复杂递归问题由）复杂递归问题由于要进行于要进行回溯回溯，在实，在实现过程中必须现过程中必须借助栈借助栈来管理和记忆来管理和记忆回溯点回溯点。2929（1 1）简单递归问题非递归实现）简单递归问题非递归实现将原问题将原问题分解分解成若干结构与原问题相同，但规模较小的

27、成若干结构与原问题相同，但规模较小的子问题，并建立原问题与子问题解之间的子问题，并建立原问题与子问题解之间的递推关系递推关系，然，然后定义若干变量用于记录递推关系的每个子问题的解；后定义若干变量用于记录递推关系的每个子问题的解；程序的执行便是根据递推关系，不断修改这些变量的值，程序的执行便是根据递推关系，不断修改这些变量的值，使之成为更大子问题的解的过程；当得到原问题解时，使之成为更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。递推过程便可结束了。3030阶乘问题的非递归算法的实现阶乘问题的非递归算法的实现intFact(intn)inti,fac;fac=1;/*将变量将变量fa

28、c初始化为初始化为Fact(0)的值的值*/for(i=1;i13232floatp(intn,floatx)floatp1,p2;if(n=0)return(1.0);/终止条件终止条件elseif(n=1)return(x);/终止条件终止条件elsep1=(2*n-1)*x*p(n-1,x);p2=(n-1)*p(n-2,x);return(p1-p2)/n);勒让德多项式的递归算法勒让德多项式的递归算法3333如果仍然采用如果仍然采用p(n,x)表示第表示第n阶勒让德多项式的值，则在阶勒让德多项式的值，则在i1的情况下的情况下有如下递推关系成立有如下递推关系成立：p(i,x)=(2i-

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

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

31、0)return(1.0);elseif(n=1)return(x);3535elsepre1=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);勒让德多项式的非递归算法勒让德多项式的非递归算法3636复杂递归程序到非递归程序的转换复杂递归程序到非递归程序的转换复杂递归问题在求解的过程中无法保证求解复杂递归问题在求解的过程中无法保证求解动作一直向前，动作一直向前，往往需要设置一些回溯点往往需要设置一些回溯点，当求解无法进行下去或当前处理的

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

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

34、归和非递归算法实现该遍历问题。leftmid-1midmid+1rightleftmid-1midmid+1right3939#defineMAXSIZE20typedefintlistarrMAXSIZE;voidlistorder(listarrlist,intleft,intright)intmid;if(left=right)mid=(left+right)/2;coutlistmid“”;listorder(list,left,mid-1);listorder(list,mid+1,right);递归实现算法递归实现算法4040#defineMAXSIZE20typedefintli

35、starrMAXSIZE;voidlistorder(listarrlist,intleft,intright)typedefstructintl;/*存放待处理数组段的起点下标存放待处理数组段的起点下标*/intr;/*存放待处理数组段的终点下标存放待处理数组段的终点下标*/stacknode;/*栈中每个元素的类型栈中每个元素的类型*/stacknodestackMAXSIZE;inttop,i,j,mid;/*top为栈顶指针为栈顶指针*/非递归实现算法非递归实现算法4141if(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-;42424343