递归程序的设计

《递归程序的设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈的应用举例—递归1递归的定义子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。2递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。3递归的要素⑴递归边界条件：确定递归到何时终止，也称为递归出口；⑵递归模式：大问题是如何分解为小问题的，也称为递归体。栈的应用举例—递归例1阶乘函数递归算法intfact(intn){if(n==0)return1;elseret

2、urnn*fact(n-1);}-*=时当时当)!1(1!n≥1n＝1nnn栈的应用举例—递归求解阶乘n!的过程计算fact(4)计算4*fact(3)计算3*fact(2)计算2*fact(1)计算fact(1)递归调用回归求值返回24返回6返回2返回1栈的应用举例—递归递归过程与递归工作栈递归过程在实现时，需要自己调用自己。层层向下递归，返回次序正好相反：递归调用n!(n-1)!(n-2)!1!=1返回次序栈的应用举例—递归递归的经典问题——汉诺塔问题在世界刚被创建的时候有一座钻石宝塔（塔A），其

3、上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。栈的应用举例—递归汉诺塔问题的递归求解:如果n=1，则将这一个盘子直接从塔A移到塔C上。否则，执行以下三步：⑴将塔A上的n-1个碟子借助塔C先移到塔B上；⑵把塔A上剩下的一个碟子移到塔C上；⑶将n-1

4、个碟子从塔B借助于塔A移到塔C上。栈的应用举例—递归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);}}栈的应用举例—递归递归函数的内部执行过程每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。局部变量返回地址值参活动记录框架递归工作记录⑴运行开始时，首先为递归调用建立

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,

6、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)结束哪些类型的问题适合于用递归方法求解?必须同时具备以下两个条件：一个问题可以化解为若干个性质相同，解法相同的小问题，而小问题还可以分解为更小的问题，……上述转化局用相同的规律，并使问题逐步简化。当问题规模降低到一定程度时是可以直接求解的（终止条件），即存在

7、明确的递归出口。据此，以下类型的问题可以考虑采用递归方法求解：数学上定位为递归的函数数据的结构是递归的例如，单链表，它的每个结点的指针域指向下一个结点，又是一个单链表；树形结构等等3)解题的方式用递归比用递推解法简单例如，汉诺塔问题，八皇后问题等如何设计递归程序递归算法设计的关键在于,找出递归方程和递归终止条件(边界条件).递归关系就是使问题向边界条件转化的过程.因此,递归关系必须能使问题越来越简单,规模越小.因此,递归算法设计,通常有以下3个步骤:      (1)分析问题,得出递归关系.   

8、   (2)设置边界条件,控制递归.      (3)设计函数,确定参数.有关递归的知识点1.什么是递归程序？递归程序的优缺点是什么？它在执行时应借助于什么来完成？其入口语句、出口语句一般用什么语句实现？1)一个函数在结束之前，直接或间接调用自身称为递归。2)优点：程序结构简单、清晰，易证明其正确性。缺点：难以理解，执行中占内存空间较多，运行效率低3)递归程序在执行中需借助栈来实现。4)递归程序的入口语句和出口语句一般用条件判断语句来实现。递归程序由基