数据结构(C++)--递归

1/44EssentialofLectureSix：一、递归二、汉诺塔问题三、递归与非递归的转化难点2/44一、递归递归是程序设计中最有力的方法之一。优点：采用递归编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。问题：编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？3/44一、递归递归:在定义自身的同时又出现了对自身的调用。直接递归函数:如果一个函数在其定义体内直接调用自己，则称直接递归函数。间接递归函数：如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称间接递归函数。4/44数学中常常利用递归手段来定义一些概念，如求阶乘的运算。n的阶乘定义为：n*(n–1)!n0n!=1n=0例如:显然，该递归的出口是0!=1。5/44求阶乘的算法如下：longfac(intn){longp;if(n==0||n==1)p=1;elsep=n*fac(n-1);returnp;}voidmain(){longx=fac(5);coutx;}6/44求阶乘的算法如下：longfac(intn){longp;if(n==0||n==1)p=1;elsep=n*fac(n-1);returnp;}递归函数包含：1、递归调用语句，如fac(n-1)；2、基值判断，如n==0||n==1即为基值，保证了递归可以终止，满足基值条件后的计算p=1,一般称为最终计算；3、调用之后的返回处理。如p=n*fac(n-1)，是返回之后要进行的操作。7/44fac(5)main()n=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层递归应返回至“上一层”，即第i-1层。递归层次:8/44为了保证递归函数正确执行，系统需设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区。每一层递归所需信息构成一个“工作记录”，其中包括所有的实参、所有的局部变量以及上一层的返回地址。每进入一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归就从栈顶弹出一个工作记录，则当前执行层的工作记录必须是递归工作栈栈顶的工作记录，称这个记录为“活动记录”，并称指示活动记录的栈顶指针为“当前环境指针”。递归工作栈9/44分治算法分治算法与软件设计的模块化方法类似。为了解决一个大的问题，将一个规模为n的问题分解为规模较小的子问题，这些子问题互相独立并且和原问题相同。分别解这些子问题，最后将将各个子问题的解合并得到原问题的解。子问题通常与原问题相似，可以递归地使用分治策略来解决。。10/44例：Hanoi塔问题传说在古代印度的贝拿勒圣庙里，安装着三根插至黄铜板上的宝石针，印度主神梵天在其中一根针上从下到上由大到小的顺序放64片金圆盘，称为梵塔，然后要僧侣轮流值班把这些金圆盘移到另一根针上，移动时必须遵守如下规则：（1）每次只能移动一个盘片；（2）任何时候大盘片不能压在小盘片之上；（3）盘片只允许套在三根针中的某一根上。这位印度主神号称如果这64片盘全部移到另一根针上时，世界在一声霹雳中毁灭，Hanoi塔问题又称“世界末日”问题。下图为3阶Hanoi塔的初始情况。abc1号盘2号盘3号盘11/44n阶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)。abc1号盘2号盘3号盘12/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=2[2T(n-2)+1]+1=22T(n-2)+1+2……=2nT(n-n)+1+2+…+2n-1=2n-113/44二、汉诺塔问题的递归算法voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}0123456789voidmove(charx,intn,chary){cout移动n号盘子从柱子x到柱子y;}14/44Hanoi(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时可以直接求解15/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc1,2,4,51递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态盘号12316/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc1,2,4,52递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态6,2,a,c,b盘号12317/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc1,2,3,93递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态6,2,a,c,b6,1,a,b,c盘号12318/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc6,72递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态6,2,a,c,b盘号12319/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc1,2,3,93递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态6,2,a,c,b8,1,c,a,b盘号12320/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc8,92递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态6,2,a,c,b盘号12321/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc6,71递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态盘号12322/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc1,2,4,52递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态8,2,b,a,c盘号12323/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc1,2,3,93递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态8,2,b,a,c8,1,b,c,a盘号12324/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc6,72递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态8,2,b,a,c盘号12325/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc1,2,3,93递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态8,2,b,a,c8,1,a,b,c盘号12326/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc8,92递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态8,2,b,a,c盘号12327/44voidHanoi(intn,charx,chary,charz){if(n==1)move(x,1,z);else{Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);}}01234567890,3,a,b,cabc8,91递归层次运行语句序号递归工作栈状态（返址，盘号，x,y,z）塔与圆盘的状态盘号12328/44voidHanoi(intn,charx,chary,charz){if(n==1)mo