递归栈的应用课件

3.33.3递归递归(栈的应用栈的应用).递归的定义递归的定义.基本思想基本思想.递归要素递归要素.递归应用举例递归应用举例阶乘函数阶乘函数汉诺塔问题汉诺塔问题.递归递归递归递归1 1、递归、递归（recursion）的定义的定义递归：递归：子程序（或函数）子程序（或函数）直接调用自己直接调用自己或通过一系列或通过一系列调用语句调用语句间接调用自己间接调用自己，是一种描述问题和解决问题，是一种描述问题和解决问题的基本方法。的基本方法。递归按其调用方式可分为递归按其调用方式可分为直接递归直接递归和和间接递归间接递归：1、直接递归直接递归:自己调用自己。如：自己调用自己。如：voidf(n)f(n/2);2、间接递归间接递归：P调用调用D，D调用调用P；如：如：voidP(intn)voidD(intn)D(n/3);P(n/2);2、递归的基本思想递归的基本思想问题分解问题分解：把一个不能或不好解决的大问题：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问进一步分解成更小的小问题，直至每个小问题都可以直接解决。题都可以直接解决。3、递归的要素、递归的要素 递归边界条件：递归边界条件：确定递归到何时终止，确定递归到何时终止，也称为递归也称为递归出口出口；递归模式递归模式：大问题是如何分解为小问题：大问题是如何分解为小问题的，也称为递归体。的，也称为递归体。例例1、定义是递归的：、定义是递归的：（）阶乘函数（）阶乘函数递归算法递归算法longunsignedfact(intn)if(n=0)return1;elsereturnn*fact(n-1);-*=时时当当时时当当 )!1(1!n1n0nnn、递归应用举例、递归应用举例求解阶乘求解阶乘n!的过程的过程计算计算计算计算 fact(4)计算计算 4*fact(3)计算计算 3*fact(2)计算计算 2*fact(1)计算计算 fact(1)递递递递归归归归调调调调用用用用回回回回归归归归求求求求值值值值返回返回 24返回返回 6返回返回 2返回返回1（2）Fibonacci数列数列0n=0Fib(n)=1n=1Fib(n-1)+Fib(n-2)n1011235813递归算法递归算法longunsignedFib(intn)if(n=0|n=1)returnn;/递归出口递归出口elsereturnFib(n-1)+Fib(n-2);/递归调用递归调用注：累计递归调用次数：注：累计递归调用次数：2*Fib(n+1)-1。例、问题的解法是递归的：例、问题的解法是递归的：利用利用递归思想递归思想来求解某类问题（本身没有来求解某类问题（本身没有明显的递归结构，但明显的递归结构，但操作方法可操作方法可以以用递归用递归很好很好的的描述描述）使其更为简单。）使其更为简单。如：汉诺塔问题、背包问题、八皇后问题等。如：汉诺塔问题、背包问题、八皇后问题等。（3）有的数据结构如二叉树、广义表、图等（如）有的数据结构如二叉树、广义表、图等（如树的遍历、图的搜索）定义。树的遍历、图的搜索）定义。经典问题经典问题汉诺塔问题汉诺塔问题 在世界刚被创建的时候有一座钻石宝塔（塔在世界刚被创建的时候有一座钻石宝塔（塔A），其上有），其上有64个个金碟。所有碟子按金碟。所有碟子按从大到小从大到小的的次序从塔底堆放至塔顶。紧挨着这座塔有另外次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔两个钻石宝塔（塔B和塔和塔C）。从世界创始之日）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔起，婆罗门的牧师们就一直在试图把塔A上的碟上的碟子移动子移动到到塔塔C上去，其间上去，其间借借助于塔助于塔B的帮助。每的帮助。每次只能移动一个碟子，任何时候都不能把一个次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。务时，世界末日也就到了。汉诺塔问题汉诺塔问题的递归的递归求解方法求解方法:如如果果n=1，则则将将这这一一个个盘盘子子直直接接从从塔塔A移移到到塔塔C上。否则，执行以下三步：上。否则，执行以下三步：将塔将塔A上上的的n-1个个碟子碟子借助塔借助塔C先移先移到塔到塔B上；上；把把塔塔A上剩下的一个碟子上剩下的一个碟子移到塔移到塔C上；上；将将n-1个个碟子碟子从塔从塔B借借助于助于塔塔A移移到塔到塔C上。上。算法实现：算法实现：voidHanoi(intn,charA,charB,charC)if(n=1)Move(A,C);elseHanoi(n-1,A,C,B);Move(A,C);Hanoi(n-1,B,A,C);Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束结束 汉诺塔递归调用过程：汉诺塔递归调用过程：、递归过程与递归工作栈、递归过程与递归工作栈非递归函数的调用，在函数调用前要保存以下非递归函数的调用，在函数调用前要保存以下三方面的信息：三方面的信息：（）返回地址（）返回地址（）本函数调用时，与形参结合的实参值，（）本函数调用时，与形参结合的实参值，包括函数名和函数参数。包括函数名和函数参数。（）本函数的局部变量值。（）本函数的局部变量值。递归函数调用也须保存这些信息，使用递归函数调用也须保存这些信息，使用“递归递归工作栈工作栈”来处理。来处理。活动记录：活动记录：栈顶栈顶的工作记录必定是当前正在执的工作记录必定是当前正在执行的工作记录行的工作记录n递归过程在实现时，需要递归过程在实现时，需要自己调用自己自己调用自己。n层层向下递归，层层向下递归，返回次序返回次序正好正好相反相反：递归调用递归调用 n!(n-1)!(n-2)!1!=1 返回次序返回次序递归函数的内部执行过程递归函数的内部执行过程n每一次递归调用时，需要为过程中每一次递归调用时，需要为过程中使用的使用的参数、局部变量参数、局部变量等另外分配存储空间。等另外分配存储空间。n每层每层递归调用递归调用需分配的空间形成递归工作需分配的空间形成递归工作记录，按记录，按后进先出后进先出的栈组织。的栈组织。局部变量局部变量返回地址返回地址值值 参参活动活动记录记录框架框架递归递归工作记录工作记录 运行开始时，首先为递归调用运行开始时，首先为递归调用建立一个工作栈建立一个工作栈，其，其结构包括结构包括值参、局部变量和返回地址值参、局部变量和返回地址；每每次次执执行行递递归归调调用用之之前前，把把递递归归函函数数的的值值参参和和局局部部变量的当前值以及调用后的返回地址压栈变量的当前值以及调用后的返回地址压栈；每每次次递递归归调调用用结结束束后后，将将栈栈顶顶元元素素出出栈栈，使使相相应应的的值值参参和和局局部部变变量量恢恢复复为为调调用用前前的的值值，然然后后转转向向返返回回地地址指定的位置继续执行址指定的位置继续执行。如：求解阶乘如：求解阶乘n!，递归工作仅需保留个参数：，递归工作仅需保留个参数：函数名函数名fact，参数，参数n，局部变量，局部变量x（存放（存放fact(n-1)的值）的值）和和y（存放（存放n*fact(n-1)的值）。的值）。参见参见P103.、消除递归（、消除递归（P103）原因：递归算法时间效率较差。原因：递归算法时间效率较差。（）（）尾递归和单向递归尾递归和单向递归算法，用带算法，用带循环结构循环结构的算法来代替。的算法来代替。（）用（）用自定义栈自定义栈来模拟系统运行时的栈，保来模拟系统运行时的栈，保存相关信息，用非递归算法来模拟递归算法。存相关信息，用非递归算法来模拟递归算法。实例分析：实例分析：（）（）尾递归：尾递归：递归调用语句只有一个，且处递归调用语句只有一个，且处于函数的最后。（可不用栈来存取相关信息）于函数的最后。（可不用栈来存取相关信息）如阶乘求解的非递归算法：如阶乘求解的非递归算法：longunsignedfact(intn)longunsignedintf=1;for(inti=1;i=2的情况的情况for(inti=2;i=n;i+)fn=f1+f2;f1=f2;f2=fn;returnfn;时间复杂度时间复杂度O(n)（）利用栈来模拟系统运行时的栈（）利用栈来模拟系统运行时的栈汉诺塔非递归算法（汉诺塔非递归算法（了解了解）：/Datatype.h#ifndefDatatype_H#defineDatatype_HclassDatatypepublic:shortintno;/存放一个标识，存放一个标识，0表示直接移动一个圆盘表示直接移动一个圆盘intndisk;/为为1表示需进一步分解；表示需进一步分解；charSPeg;/参数参数AcharAPeg;/参数参数BcharDPeg;/参数参数C;#endifvoidhanoi2(intn,chara,charb,charc)SeqStackS1;DatatypeH,H1;H.no=1;H.ndisk=n;H.SPeg=a;H.APeg=b;H.DPeg=c;S1.Push(H);/初始入栈初始入栈while(!S1.Empty()if(S1.GetTop().no=1&S1.GetTop().ndisk!=1)/退栈退栈hanoi(n,a,b,c);将将hanoi(n-1,a,c,b)操作参数进栈操作参数进栈H.ndisk=S1.GetTop().ndisk-1;H.SPeg=S1.GetTop().SPeg;H.APeg=S1.GetTop().APeg;H.DPeg=S1.GetTop().DPeg;S1.Pop();H1.no=1;H1.ndisk=H.ndisk;H1.SPeg=H.APeg;H1.APeg=H.SPeg;H1.DPeg=H.DPeg;S1.Push(H1);/等价于等价于move(n,a,c);H1.no=0;H1.ndisk=H.ndisk+1;H1.SPeg=H.SPeg;H1.APeg=H.DPeg;S1.Push(H1);/等价于等价于hanoi(n-1,b,a,c)操作参数进栈操作参数进栈H1.no=1;H1.ndisk=H.ndisk;H1.SPeg=H.SPeg;H1.APeg=H.DPeg;H1.DPeg=H.APeg;S1.Push(H1);/处理处理move(n,a,c);输出及当只剩一个盘时的移动信息输出及当只剩一个盘时的移动信息while(!S1.Empty()&(S1.GetTop().no=0)|(S1.GetTop().ndisk=1)/将第将第n个圆盘从个圆盘从a移到移到c退栈退栈if(!S1.Empty()&(S1.GetTop().no=0)cout将第将第S1.GetTop().ndisk个盘片从个盘片从S1.GetTop().SPeg移动到移动到S1.GetTop().APegendl;S1.Pop();if(!S1.Empty()&(S1.GetTop().ndisk=1)/hanoi(1,a,b,c)退栈退栈cout将第将第S1.GetTop().ndisk个盘片从个盘片从S1.GetTop().SPeg移动到移动到“S1.GetTop().DPegendl;S1.Pop();/Main.cpp#include/引用输入输出流引用输入输出流#includeSeqStack.cpp/引入成员函数文件引入成员函数文件#includeDatatype.husingnamespacestd;voidmain()hanoi2(3,A,B,C);小结：小结：递归算法的递归算法的缺点缺点：费时、费内存空间，效率：费时、费内存空间，效率往往很低。往往很低。递归算法的递归算法的优点优点：它能使一个蕴含递归关系：它能使一个蕴含递归关系且结构复杂的程序简洁、清晰、精炼、增加且结构复杂的程序简洁、清晰、精炼、增加可读性。可读性。