辽宁石油化工大学数据结构课件递归与广义表.ppt

《辽宁石油化工大学数据结构课件递归与广义表.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

3、link);}fffffa0a1a2a3a4递归找链尾在链表中寻找等于给定值的结点并打印其数值templatevoidPrint(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柱上的

4、(n-1)个盘子移到B柱上：②将A柱上最后一个盘子直接移到C柱上；③用A柱做过渡，将B柱上的(n-1)个盘子移到C柱上。#include#include"strclass.h”voidHanoi(intn,StringA,StringB,StringC){//解决汉诺塔问题的算法if(n==1)cout<<"move"<

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

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

7、etLoc2return1//返回1RetLoc2return1*1//返回1RetLoc2return2*1//返回2递归过程改为非递归过程递归过程简洁、易编、易懂递归过程效率低，重复计算多改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法longFib(longn){if(n<=1)returnn;elsereturnFib(n-1)+Fib(n-2);}如F0=0,F1=1,F2=1,F3=2,F4=3,

8、F5=5调用次数NumCall(k)=2*Fib(k+1)-1。斐波那契数列的递归调用树Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fi