资源描述：
《(数据结构)九讲 递归及其应用ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第九讲递归本讲主要内容：递归的定义递归的工作原则递归的执行过程递归和非递归程序的差异递归的应用递归的定义递归：子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，称为递归。递归是一种描述问题和解决问题的基本方法。例如：voidA(){…A();…}函数A中的语句直接调用了函数A本身，这叫做直接递归调用。递归的定义递归的定义voidB()voidC(){…{…C();B();……}}在函数B中调用了函数C，而在函数C中又调用了B，这两个函数都通过另一个函数调用了它们自己，这就叫做间接递归调用。递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，
2、再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。递归的要素⑴递归边界条件：确定递归到何时终止，也称为递归出口；⑵递归模式：大问题是如何分解为小问题的，也称为递归体。例1阶乘函数递归算法intfact(intn){if(n==0)return1;elsereturnn*fact(n-1);}-*=时当时当)!1(1!n≥1n＝0nnn应用举例—递归求解阶乘n!的过程计算fact(4)计算4*fact(3)计算3*fact(2)计算2*fact(1)计算fact(1)递归调用回归求值返回24返回6返回2返回1应用举例—递归递归过程与递归工作栈递归过程在实现时
3、，需要自己调用自己。层层向下递归，返回次序正好相反：递归调用n!(n-1)!(n-2)!1!=1返回次序应用举例—递归递归函数的内部执行过程每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。局部变量返回地址值参活动记录框架递归工作记录⑴运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；⑵每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；⑶每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位
4、置继续执行。应用举例—递归例2.Fibonacci数列求解.0,当n=0f(n)=1,当n=1f(n-1)+f(n-2),当n>10,1,1,2,3,5,8,13,21…….非递归求解:intf(intn){intpre,now,next,j;if(n<=1)return(n);else{pre=0;now=1;for(j=2;j<=n;j++){next=pre+now;pre=now;now=next;}return(next);}}递归求解:intf(intn){if(n<=1)return(n);elsereturn(f(n-1)+f(n-2));}递归程序与非递归程
5、序的差异递归与非递归程序的差别主要在于返回数据和备忘录的内存需求量.一般来说，非递归程序在时间及空间上都比递归程序有效.在解决复杂问题的时候,可以侧重于用递归求解.递归与非递归的比较递归非递归程序可读性易难执行物大小小大时间长短占用堆栈大小递归的应用回文串汉诺塔问题迷宫问题N皇后问题回文串如果一个字符串从左向右读和从右向左读完全相同（不区分大小写），则这个字符串称为回文串（palindrome)，例如“noon”、“madam”等都是回文串。可以用递归方法检测一个字符串S是否为回文串。设S=“ShSh+1….St-1St”,h是第一个字符的位置，t是最后一个字符的位置。1)若
6、S是空串或长度为1，则S为回文串，否则：2)若Sh≠St，则S不是回文串，否则，递归地检测S的子串“Sh+1….St-1”.回文串boolpalindrome(string&s,unsignedh,unsignedt){if(h>=t)return1;if(tolower(s[h])==tolower(s[t]))returnpalindrome(s,h+1,t-1);elsereturn0;}递归的经典问题——汉诺塔问题在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界
7、创始之日起，婆罗门的牧师们就一直在试图把塔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
