数据结构C递归.ppt

1/44,一、递归,递归是程序设计中最有力的方法之一。优点：采用递归编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。问题：编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？,2/44,一、递归,递归:在定义自身的同时又出现了对自身的调用。直接递归函数:如果一个函数在其定义体内直接调用自己，则称直接递归函数。间接递归函数：如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间接递归函数。,3/44,数学中常常利用递归手段来定义一些概念，如求阶乘的运算。n的阶乘定义为：n*(n 1)!n0 n!=1 n=0,例如:,显然，该递归的出口是 0!=1。,4/44,求阶乘的算法如下：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);coutx;,5/44,求阶乘的算法如下：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)，是返回之后要进行的操作。,6/44,fac(2)=2,fac(1)=1,fac(3)=6,fac(4)=24,fac(5)=120,输出,假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第 i层递归调用本身为进入“下一层”，即第 i+1 层。反之，退出第 i 层递归应返回至“上一层”，即第 i-1 层。,递归层次:,7/44,为了保证递归函数正确执行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有的实参、所有的局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归就从栈顶弹出一个工作记录，则当前执行层的工作记录必须是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。,递归工作栈,8/44,分治算法,分治算法与软件设计的模块化方法类似。为了解决一个大的问题，将一个规模为n的问题分解为规模较小的子问题，这些子问题互相独立并且和原问题相同。分别解这些子问题，最后将将各个子问题的解合并得到原问题的解。子问题通常与原问题相似，可以递归地使用分治策略来解决。,9/44,例：Hanoi塔问题,传说在古代印度的贝拿勒圣庙里，安装着三根插至黄铜板上的宝石针，印度主神梵天在其中一根针上从下到上由大到小的顺序放64片金圆盘，称为梵塔，然后要僧侣轮流值班把这些金圆盘移到另一根针上，移动时必须遵守如下规则：（1）每次只能移动一个盘片；（2）任何时候大盘片不能压在小盘片之上；（3）盘片只允许套在三根针中的某一根上。这位印度主神号称如果这64片盘全部移到另一根针上时，世界在一声霹雳中毁灭，Hanoi塔问题又称“世界末日”问题。下图为3阶Hanoi塔的初始情况。,10/44,n阶Hanoi塔问题Hanoi(n,a,b,c)，当n=0时，没盘子可供移动，什么也不做；当n=1时，可直接将1号盘子从a轴移动到c轴上；当n=2时，可先将1号盘子移动到b轴，再将2号盘子移动到c轴，最后将1号盘子移动到c轴；对于一般n0的一般情况可采用如下分治策略进行移动（1）将1至n-1号盘从 a 轴移动至 b 轴，可递归求解Hanoi(n-1,a,c,b)；（2）将 n号盘从 a 轴移动至 c 轴；（3）将1至n-1号盘从b轴移动至c轴，可递归求解 Hanoi(n-1,b,a,c)。,11/44,例：分析Hanoi塔问题移动圆盘的次数,设T(n)表示n个圆盘的Hanoi塔问题移动圆盘的次数，显然T(0)=0，对于n0的一般情况采用如下分治策略：（1）将1至n-1号盘从 a 轴移动至 b 轴，可递归求解Hanoi(n-1,a,c,b)；（2）将 n号盘从 a 轴移动至 c 轴；（3）将1至n-1号盘从b轴移动至c轴，可递归求解 Hanoi(n-1,b,a,c)。在（1）与（3）中需要移动圆盘次数T(n-1)，（2）需要移动一次圆盘。可得如下的关系：T(n)=2T(n-1)+1展开上式可得：T(n)=2T(n-1)+1=22T(n-2)+1+1=22T(n-2)+1+2=2nT(n-n)+1+2+2n-1=2n-1,12/44,二、汉诺塔问题的递归算法,void move(char x,int n,char y)cout移动n号盘子从柱子x到柱子y;,13/44,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时可以直接求解,14/44,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);,0123456789,1,2,4,5,1,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,15/44,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);,0123456789,0,3,a,b,c,1,2,4,5,2,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,6,2,a,c,b,16/44,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);,0123456789,0,3,a,b,c,1,2,3,9,3,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,6,2,a,c,b,6,1,a,b,c,17/44,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);,0123456789,0,3,a,b,c,6,7,2,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,6,2,a,c,b,18/44,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);,0123456789,0,3,a,b,c,1,2,3,9,3,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,6,2,a,c,b,8,1,c,a,b,19/44,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);,0123456789,0,3,a,b,c,8,9,2,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,6,2,a,c,b,20/44,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);,0123456789,0,3,a,b,c,6,7,1,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,21/44,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);,0123456789,0,3,a,b,c,1,2,4,5,2,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,8,2,b,a,c,22/44,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);,0123456789,0,3,a,b,c,1,2,3,9,3,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,8,2,b,a,c,8,1,b,c,a,23/44,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);,0123456789,0,3,a,b,c,6,7,2,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,8,2,b,a,c,24/44,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);,0123456789,0,3,a,b,c,1,2,3,9,3,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,8,2,b,a,c,8,1,a,b,c,25/44,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);,0123456789,0,3,a,b,c,8,9,2,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,8,2,b,a,c,26/44,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);,0123456789,0,3,a,b,c,8,9,1,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,27/44,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);,0123456789,栈空,0,递归层次,运行语句序号,递归工作栈状态（返址，盘号，x,y,z）,塔与圆盘的状态,28/44,三、递归程序到非递归程序的转换,选择递归 还是 非递归：采用递归方式实现问题的算法程序具有结构清晰、读性好、易于理解等优点，但递归程序较之非递归程序无论是空间需求还是时间需求都更高，因此在希望节省存储空间和追求执行效率的情况下，人们更希望使用非递归方式实现问题的算法程序。,29/44,求解递归问题的两种方式,（1）在求解过程中直接求值，无需回溯。称这类递归问题为简单递归问题；（2）另一类递归问题在求解过程中不能直接求值，必须进行试探和回溯，称这类递归问题为复杂递归问题。,转换方法不同：（1）简单递归问题可以采用递推方法直接求解；（2）复杂递归问题由于要进行回溯，在实现过程中必须借助栈来管理和记忆回溯点。,30/44,（1）简单递归问题非递归实现,将原问题分解成若干结构与原问题相同，但规模较小的子问题，并建立原问题与子问题解之间的递推关系，然后定义若干变量用于记录递推关系的每个子问题的解；程序的执行便是根据递推关系，不断修改这些变量的值，使之成为更大子问题的解的过程；当得到原问题解时，递推过程便可结束了。,31/44,阶乘问题的非递归算法的实现,int Fact(int n)int i,fac;fac=1;/*将变量fac初始化为Fact(0)的值*/for(i=1;i=n;+i)fac=i*fac;/*根据递推关系进行递推*/return(fac);,32/44,例 试编写两个函数，分别使用递归方式和非递归方式求第n阶勒让德多项式的值。已知勒让德多项式的递归定义如下：1 n=0pn(x)=x n=1(2n-1)xpn-1(x)(n-1)pn-2(x)/n n1,33/44,float 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);,勒让德多项式的递归算法,34/44,如果仍然采用p(n,x)表示第n阶勒让德多项式的值，则在i1的情况下有如下递推关系成立：p(i,x)=(2i-1)xp(i-1,x)(i-1)p(i-2,x)/i 显然，可以利用以上递推关系，从i=2开始，逐步增大i的值，依次求解第i阶勒让德多项式的值；当i=n时，便求到了p(n,x)的值。在整个求解过程中不需要进行试探和回溯，因而该问题属于简单递归问题，完全可以使用递推技术加以实现。,勒让德多项式的非递归实现,35/44,定义两个变量pre1和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 pre1,pre2,a,b,valuep;int i;if(n=0)return(1.0);else if(n=1)return(x);,36/44,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);,勒让德多项式的非递归算法,37/44,复杂递归程序到非递归程序的转换,复杂递归问题在求解的过程中无法保证求解动作一直向前，往往需要设置一些回溯点，当求解无法进行下去或当前处理的工作已经完成时，必须退回到所设置的回溯点，继续问题的求解。因此，在使用非递归方式实现一个复杂递归问题的算法时，经常使用栈来记录和管理所设置的回溯点。,38/44,按中点优先的顺序遍历线性表问题：已知线性表list以顺序存储方式存储，要求按以下顺序输出list中所有结点的值：首先输出线性表list中点位置上的元素值，然后输出中点左部所有元素的值，再输出中点右部所有元素的值；而无论输出中点左部所有元素的值还是输出中点右部所有元素的值，也均应遵循以上规律。,例如：,39/44,例如，已知数组list中元素的值为：18 32 04 09 26 06 10 30 12 08 45则list中元素按中点优先顺序遍历的输出结果为：06 04 18 32 09 26 12 10 30 08 45试采用递归和非递归算法实现该遍历问题。,40/44,#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);,递归实现算法,41/44,#define MAXSIZE 20typedef int listarrMAXSIZE;void listorder(listarr list,int left,int right)typedef struct int l;/*存放待处理数组段的起点下标*/int r;/*存放待处理数组段的终点下标*/stacknode;/*栈中每个元素的类型*/stacknode stackMAXSIZE;int top,i,j,mid;/*top为栈顶指针*/,非递归实现算法,42/44,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-;,