《递归的概念递归过程与递归工作栈递归与回溯广义表.ppt》由会员分享，可在线阅读，更多相关《递归的概念递归过程与递归工作栈递归与回溯广义表.ppt（61页珍藏版）》请在三一办公上搜索。
1、递归的概念递归过程与递归工作栈递归与回溯广义表,第五章 递归与广义表,递归的概念,递归的定义 若一个对象部分地包含它自己,或用它自己给自己定义,则称这个对象是递归的；若一个过程直接地或间接地调用自己,则称这个过程是递归的过程。以下三种情况常常用到递归方法。定义是递归的 数据结构是递归的 问题的解法是递归的,定义是递归的,求解阶乘函数的递归算法long Factorial(long n)if(n=0)return 1;else return n*Factorial(n-1);,例如，阶乘函数,求解阶乘 n!的过程,主程序 main:fact(4),参数 4 计算 4*fact(3)返回 24,参
2、数 3 计算 3*fact(2)返回 6,参数 2 计算 2*fact(1)返回 2,参数 1 计算 1*fact(0)返回 1,参数 0 直接定值=1 返回 1,参数传递,结果返回,递归调用,回归求值,数据结构是递归的,一个结点，它的指针域为NULL，是一个单链表;一个结点，它的指针域指向单链表，仍是一个单链表。,例如，单链表结构,f,f,搜索链表最后一个结点并打印其数值template void Print(ListNode*f)if(f-link=NULL)cout data link);,f,f,f,f,f,a0,a1,a2,a3,a4,递归找链尾,在链表中寻找等于给定值的结点并打印其
3、数值template void Print(ListNode*f,Type,f,f,f,f,递归找含x值的结点,x,问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题的解法：如果 n=1，则将这一个盘子直接从 A 柱移到 C 柱上。否则，执行以下三步：用 C 柱做过渡，将 A 柱上的(n-1)个盘子移 到 B 柱上：将 A 柱上最后一个盘子直接移到 C 柱上；用 A 柱做过渡，将 B 柱上的(n-1)个盘子移 到 C 柱上。,#include#include strclass.h”void Hanoi(int n,String A,String B,String C)/解决汉
4、诺塔问题的算法 if(n=1)cout move A to C endl;else Hanoi(n-1,A,C,B);cout move A to C endl;Hanoi(n-1,B,A,C);,递归过程与递归工作栈,递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反：递归调用 n!(n-1)!(n-2)!1!0!=1 返回次序主程序第一次调用递归过程为外部调用；递归过程每次递归调用自己为内部调用。它们返回调用它的过程的地址不同。,递归工作栈,每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织
5、。,局部变量返回地址参 数,活动记录框架,递归工作记录,函数递归时的活动记录,.,Function().,调用块,函数块,返回地址(下一条指令)局部变量 参数,long Factorial(long n)int temp;if(n=0)return 1;else temp=n*Factorial(n-1);RetLoc2 return temp;,void main()int n;n=Factorial(4);RetLoc1,计算Fact时活动记录的内容,递归调用序列,0 RetLoc2,1 RetLoc2,2 RetLoc2,3 RetLoc2,4 RetLoc1,参数 返回地址 返回时的指
6、令,RetLoc1 return 4*6/返回24,RetLoc2 return 3*2/返回6,RetLoc2 return 1/返回1,RetLoc2 return 1*1/返回1,RetLoc2 return 2*1/返回2,递归过程改为非递归过程,递归过程简洁、易编、易懂递归过程效率低，重复计算多改为非递归过程的目的是提高效率单向递归和尾递归可直接用迭代实现其非递归过程其他情形必须借助栈实现非递归过程,计算斐波那契数列的函数Fib(n)的定义,求解斐波那契数列的递归算法 long Fib(long n)if(n=1)return n;else return Fib(n-1)+Fib(n
7、-2);,如 F0=0,F1=1,F2=1,F3=2,F4=3,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),Fib(3),Fib(5),Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),栈结点,n tag,tag=1,向左递归；tag=2,向右递归,Fib(1),Fib(0),Fib(2),
8、Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),2 13 14 1,n=1sum=0+1,2 23 14 1,n=2-2,3 14 1,n=0sum=1+0,3 24 1,n=3-2,4 1,n=1sum=1+1,4 2,n=4-2,Fib(1),Fib(0),Fib(2),Fib(1),Fib(0),Fib(2),Fib(1),Fib(3),Fib(4),2 14 2,n=1sum=2+1,2 24 2,n=2-2,4 2,n=0sum=3+0,long Fibnacci(long n)Stack S;Node*w;long sum=0;/反复执行直到所有
9、终端结点数据累加完 do while(n 1)w-n=n;w-tag=1;S.push(w);n-;/向左递归到底,边走边进栈 sum=sum+n;/执行求和,while(!S.IsEmpty()w=S.getTop();S.Pop();if(w-tag=1)/改为向右递归 w-tag=2;S.push(w);n=w-n 2;/F(n)右侧为F(n-2)break;while(!S.IsEmpty();return sum;,单向递归用迭代法实现,long FibIter(long n)if(n=1)return n;long twoback=0,oneback=1,Current;for(i
10、nt i=2;i=n;i+)Current=twoback+oneback;twoback=oneback;oneback=Current;return Current;,void recfunc(int A,int n)if(n=0)cout An“”;n-;recfunc(A,n);,25 36 72 18 99 49 54 63,尾递归用迭代法实现,void sterfunc(int A,int n)/消除了尾递归的非递归函数 while(n=0)cout value An endl;n-;,递归与回溯 常用于搜索过程,n皇后问题 在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行
11、、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。,1#主对角线3#主对角线5#主对角线,0#次对角线2#次对角线4#次对角线6#次对角线,1#次对角线3#次对角线5#次对角线,0#主对角线2#主对角线4#主对角线6#主对角线,0 1 2 3,0123,k=i+j,k=n+i-j-1,解题思路,安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探(j=0,n-1)在第 j 列安放一个皇后：如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后
12、。,设置 4 个数组 coln:coli 标识第 i 列是否安放了皇后 md2n-1:mdk 标识第 k 条主对角线是否安放了皇后 sd2n-1:sdk 标识第 k 条次对角线是否安放了皇后 qn:qi 记录第 i 行皇后在第几列,void Queen(int i)for(int j=0;j n;j+)if(第 i 行第 j 列没有攻击)在第 i 行第 j 列安放皇后；if(i=n-1)输出一个布局；else Queen(i+1);撤消第 i 行第 j 列的皇后；,算法求精void Queen(int i)for(int j=0;j n;j+)if(!colj/*在第 i 行第 j 列安放皇后
13、*/,if(i=n-1)/*输出一个布局*/for(j=0;j n;j+)cout qj,;cout endl;else Queen(i+1);colj=mdn+i-j-1=sdi+j=0;qi=0;/*撤消第 i 行第 j 列的皇后*/,广义表(General Lists),广义表的概念 n(0)个表元素组成的有 限序列，记作 LS=(a0,a1,a2,an-1)LS是表名，ai 是表元素，它可以是表(称 为子表)，可以是数据元素(称为原子)。n为表的长度。n=0 的广义表为空表。n 0时，表的第一个表元素称为广义表 的表头(head)，除此之外，其它表元素组 成的表称为广义表的表尾(tai
14、l)。,广义表的特性,有次序性有长度,A=()B=(6,2)C=(a,(5,3,x)D=(B,C,A)E=(B,D)F=(4,F),有深度可共享,可递归,广义表的表示,只包括整数和字符型数据的广义表链表表示,表中套表情形下的广义表链表表示,5,2,3,2,4,3,6,10,3,9,14,list2,5,list1,12,47,a,s,广义表结点定义,结点类型 utype=0,表头；=1,整型原子；=2,字符型原子；=3,子表值value utype=0时,存放引用计数(ref)；utype=1时,存放整数值(intinfo)；utype=2时,存放字符型数据(charinfo)；utype=3
15、时,存放指向子表表头的指针(hlink)尾指针tlink utype=0时,指向该表第一个结点；utype0时,指向同一层下一个结点,utype value tlink,广义表的存储表示,E,B,F,0 1,1 4,3,0 1,3,3,D,0 1,1 5,1 3,2 x,0 1,2 a,3,C,0 1,3,3,3,0 1,1 6,D,B,B,C,A,1 2,0 1,A,广义表的类定义,class GenList;/GenList类的前视声明class GenListNode/广义表结点类的前视声明struct Items/仅有结点信息的项friend class GenlistNode;fri
16、end class Genlist;int utype;/0/1/2/3 union/联合,int ref;/utype=0,存放引用计数 int intinfo;/utype=1,存放整数值 char charinfo;/utype=2,存放字符 GenListNode*hlink;/utype=3,存放指向子表的指针 class GenListNode/广义表结点类定义friend class Genlist;private:int utype;/0/1/2/3,GenListNode*tlink;/下一结点指针 union/联合 int ref;/utype=0,存放引用计数 int i
17、ntinfo;/utype=1,存放整数值 char charinfo;/utype=2,存放字符 GenListNode*hlink;/utype=3,存放指向子表的指针 value;public:GenListNode():utype(0),tlink(NULL),ref(0)/构造函数,建表头结点,GenListNode(int t,GenListNode*next=NULL)/构造函数：建表结点 Items,class GenList/广义表类定义 private:GenListNode*first;/广义表头指针 GenListNode*Copy(GenListNode*ls);/复
18、制一个 ls 指示的无共享非递归表 int depth(GenListNode*ls);/计算由 ls 指示的非递归表的深度 int equal(GenListNode*s,GenListNode*t);/比较以s和t为表头的两个表是否相等 void Remove(GenListNode*ls);/释放以 ls 为表头结点的广义表,public:Genlist();/构造函数 GenList();/析构函数 GenListNode/将elem2插到表中元素elem1后,void Copy(const GenList/从广义表的字符串描述 s 出发,/建立一个带表头结点的广义表结构,广义表的访问
19、算法,广义表结点类的存取成员函数Items,GenListNode,Items/返回类型及值,GenList,GenListNode*GenList:First()if(first-tlink=NULL)return NULL;else return first-tlink;GenListNode*GenList:Next(GenListNode*elem)if(elem-tlink=NULL)return NULL;else return elem-tlink;,广义表的递归算法,广义表的复制算法void GenList:Copy(const GenList,switch(ls-utype)
20、case 0:q-value.ref=ls-value.ref;break;case 1:q-value.intgrinfo=ls-value.intgrinfo;break;case 2:q-value.charinfo=ls-value.charinfo;break;case 3:q-value.hlink=Copy(ls-value.hlink);,q-tlink=Copy(ls-tlink);return q;,求广义表的深度,例如，对于广义表 E(B(a,b),D(B(a,b),C(u,(x,y,z),A(),1,1,1,1,2,3,4,int GenList:depth(GenLi
21、stNode*ls)if(ls-tlink=NULL)return 1;/空表 GenListNode*temp=ls-tlink;int m=0;while(temp!=NULL)/在表顶层横扫 if(temp-utype=3)/结点为表结点 int n=depth(temp-value.hlink);if(m tlink;return m+1;,int GenList:depth()return depth(first);,广义表的删除算法,0 1,1 5,3,3,1 2,0 1,2 x,0 1,0 1,2 y,ls,3,2 x,扫描子链表 若结点数据为x,删除。可以做循环连 续删。若结点
22、数据不为x，不执行删除。若结点为子表，递归在子表执行删除。,void delvalue(GenListNode*ls,const value x)/在广义表中删除所有含 x 的结点 if(ls-tlink!=NULL)/非空表 GenListNode*p=ls-tlink;,while(p!=NULL,delvalue(p,x);/在后续链表中删除 GenList:GenList()/析构函数 Remove(first);void GenList:Remove(GenListNode*ls)/私有函数：释放以 ls 为表头指针的广义表 ls-value.ref-;/引用计数减1,if(ls-value.ref=0)/如果减到0 GenListNode*p=ls,*q;/横扫表顶层 while(p-tlink!=NULL)q=p-tlink;/到第一个结点 if(q-utype=3)/递归删除子表 Remove(q-value.hlink);p-link=q-link;delete q;,
