递归程序的设计.pptVIP

第1页，共21页，星期日，2025年，2月5日栈的应用举例—递归1递归的定义子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。2递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。第2页，共21页，星期日，2025年，2月5日3递归的要素⑴递归边界条件：确定递归到何时终止，也称为递归出口；⑵递归模式：大问题是如何分解为小问题的，也称为递归体。栈的应用举例—递归第3页，共21页，星期日，2025年，2月5日例1阶乘函数递归算法intfact(intn){if(n==0)return1;elsereturnn*fact(n-1);}-*=时当时当)!1(1!n≥1n＝1nnn栈的应用举例—递归第4页，共21页，星期日，2025年，2月5日求解阶乘n!的过程计算fact(4)计算4*fact(3)计算3*fact(2)计算2*fact(1)计算fact(1)递归调用回归求值返回24返回6返回2返回1栈的应用举例—递归第5页，共21页，星期日，2025年，2月5日递归过程与递归工作栈递归过程在实现时，需要自己调用自己。层层向下递归，返回次序正好相反：递归调用n!(n-1)!(n-2)!1!=1返回次序栈的应用举例—递归第6页，共21页，星期日，2025年，2月5日递归的经典问题——汉诺塔问题在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。栈的应用举例—递归第7页，共21页，星期日，2025年，2月5日汉诺塔问题的递归求解:如果n=1，则将这一个盘子直接从塔A移到塔C上。否则，执行以下三步：⑴将塔A上的n-1个碟子借助塔C先移到塔B上；⑵把塔A上剩下的一个碟子移到塔C上；⑶将n-1个碟子从塔B借助于塔A移到塔C上。栈的应用举例—递归第8页，共21页，星期日，2025年，2月5日第9页，共21页，星期日，2025年，2月5日voidHanoi(intn,charA,charB,charC){??if(n==1)Move(A,C);????else{??????????????Hanoi(n-1,A,C,B);????Move(A,C);?????????Hanoi(n-1,B,A,C);??????????????}???????}栈的应用举例—递归第10页，共21页，星期日，2025年，2月5日递归函数的内部执行过程每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。局部变量返回地址值参活动记录框架递归工作记录⑴运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；⑵每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；⑶每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。栈的应用举例—递归第11页，共21页，星期日，2025年，2月5日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