数据结构讲义c语言描述第5章.ppt

《数据结构讲义c语言描述第5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归的概念递归过程与递归工作栈递归与回溯第五章递归与广义表递归的概念递归的定义若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况常常用到递归方法。定义是递归的数据结构是递归的问题的解法是递归的定义是递归的求解阶乘函数的递归算法longFactorial(longn){if(n==0)return1;elsereturnn*Factorial(n-1);}例如，阶乘函数求解阶乘n!的过程主程序main:fact(4)参数4计算4*fact(3)返回24参数3计算3*fact(2)返回6参数2计算2*f

2、act(1)返回2参数1计算1*fact(0)返回1参数0直接定值=1返回1参数传递结果返回递归调用回归求值数据结构是递归的一个结点，它的指针域为NULL，是一个单链表;一个结点，它的指针域指向单链表，仍是一个单链表。例如，单链表结构ff搜索链表最后一个结点并打印其数值templatevoidPrint(ListNode*f){if(f->link==NULL)cout<data<link);}fffffa0a1a2a3a4递归找链尾在链表中寻找等于给定值的结点并打印其数值template

3、e>voidPrint(ListNode*f,Type&x){if(f!=NULL)if(f->data==x)cout<data<link,x);}ffff递归找含x值的结点x问题的解法是递归的例如，汉诺塔(TowerofHanoi)问题的解法：如果n=1，则将这一个盘子直接从A柱移到C柱上。否则，执行以下三步：①用C柱做过渡，将A柱上的(n-1)个盘子移到B柱上；②将A柱上最后一个盘子直接移到C柱上；③用A柱做过渡，将B柱上的(n-1)个盘子移到C柱上。#include#include"strcla

4、ss.h”voidHanoi(intn,StringA,StringB,StringC){//解决汉诺塔问题的算法if(n==1)cout<<"move"<CA,B,C(1,A,C,B)A,B,CA->CA->C(1,B,A,C)A,B,CA->CA->BA->BA->CB->CC->BA->C(2,B,A,C)A,B,C(1,A,C,B)A,B,CA->CA->C(1,B

5、,A,C)A,B,CA->CB->CA->BB->AB->CA->C自顶向下、逐步分解的策略子问题应与原问题做同样的事情，且更为简单；解决递归问题的策略是把一个规模比较大的问题分解为一个或若干规模比较小的问题，分别对这些比较小的问题求解，再综合它们的结果，从而得到原问题的解。—分而治之策略（分治法）这些比较小的问题的求解方法与原来问题的求解方法一样。构成递归的条件不能无限制地调用本身，必须有一个出口，化简为非递归状况直接处理。Procedure(){if()return(initialvalue);elseretu

6、rn((parameterexchange));}递归过程与递归工作栈递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反：递归调用n!(n-1)!(n-2)!1!0!=1返回次序主程序第一次调用递归过程为外部调用；递归过程每次递归调用自己为内部调用。它们返回调用它的过程的地址不同。递归工作栈每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。局部变量返回地址参数活动记录框架递归工作记录函数递归时的活动记录……………….<下一条指令>Function(<参数表>)……………….

7、turn>调用块函数块返回地址(下一条指令)局部变量参数longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);RetLoc2returntemp;}voidmain(){intn;n=Factorial(4);RetLoc1}计算Fact时活动记录的内容递归调用序列01RetLoc211RetLoc222RetLoc236