递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件.pptx

《递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件.pptx》由会员分享，可在线阅读，更多相关《递归的概念递归过程与递归工作栈递归与回溯广义表ppt课件.pptx（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、求解阶乘函数的递归算法求解阶乘函数的递归算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1);时时当当时时当当 1 ,)!1( 0 , 1!nnnnn main : fact(4)参数参数 4 计算计算 4*fact(3) 返回返回 24参数参数 3 计算计算 3*fact(2) 返回返回 6参数参数 2 计算计算 2*fact(1) 返回返回 2参数参数 1 计算计算 1*fact(0) 返回返回 1参数参数 0 直接定值直接定值 = 1 返回返回 1f f template vo

2、id Print ( ListNode *f ) if ( f -link = NULL ) cout data link );f f f f f a0a1a2a3a4递归找链尾template void Print ( ListNode *f, Type& x ) if ( f != NULL ) if ( f - data = x ) cout data link, x );f f f f 递归找含x值的结点x#include #include strclass.h”void Hanoi (int n, String A, String B, String C) /解决汉诺塔问题的算法 i

3、f ( 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 ); 递归递归工作记录工作记录.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); RetL

4、oc1 0 RetLoc21 RetLoc22 RetLoc23 RetLoc24 RetLoc1RetLoc1 return 4*6 / RetLoc2 return 3*2 / RetLoc2 return 1 / RetLoc2 return 1*1 / RetLoc2 return 2*1 / long Fib ( long n ) if ( n = 1 ) return n; else return Fib (n-1) + Fib (n-2); 1n2),Fib(n1)Fib(n0,1nn,)Fib(n斐波那契数列的递归调用树斐波那契数列的递归调用树Fib(1)Fib(0)Fib(1

5、)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 tagtag = 1, 向左递归；向左递归；tag = 2, 向右递归向右递归Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2 13 14 1 n=1sum=0+12 23 14 1n=2-23 14 1 n=0sum=1+03 24 1n=3-24 1 n=1sum=1+14

6、2n=4-2Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(2)Fib(1)Fib(3)Fib(4)2 14 2 n=1sum=2+12 24 2n=2-24 2 n=0sum=3+0long Fibnacci ( long n ) Stack S; Node *w; long sum = 0; /反复执行直到所有终端结点数据累加完 do while ( n 1 ) w-n = n; w-tag = 1; S.push ( w ); n-; /向左递归到底, 边走边进栈 sum = sum + n; /执行求和 while ( !S.IsEmpty( ) ) w = S.g

7、etTop( ); 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 ( int i = 2; i = 0 ) cout An = 0 ) cout value An endl; n-; 1#主对角线主对角线3#

8、主对角线主对角线5#主对角线主对角线0#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线1#次对角线次对角线3#次对角线次对角线5#次对角线次对角线0#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线0 1 2 3 0123k = i+jk = n+i j- -1u u u u void Queen( int i ) for ( int j = 0; j n; j+ ) if ( ) ； if ( i = n-1 ) ； else Queen ( i+1 ); ； void Queen( int i ) for ( int j = 0;

9、j n; j+ ) if ( !colj & !mdn+i-j-1 & !sdi+j ) /*第第 i 行第行第 j 列没有攻击列没有攻击 */ colj = mdn+i-j-1 = sdi+j = 1; qi = j; /*在在第第 i 行第行第 j 列安放皇后列安放皇后*/ if ( i = n-1 ) for ( j = 0; j n; j+ ) cout qj ,; cout utype; /返回表元素elem的数据类型 GenListNode& setInfo ( Items&x ); /将表元素elem中的值修改为x;class GenList /广义表类定义 private: G

10、enListNode *first; /广义表头指针 GenListNode *Copy ( GenListNode *ls ); /复制一个 ls 指示的无共享非递归表 int depth ( GenListNode *ls ); /计算由 ls 指示的非递归表的深度 int equal (GenListNode *s, GenListNode *t); /比较以s和t为表头的两个表是否相等 void Remove (GenListNode *ls ); /释放以 ls 为表头结点的广义表public: Genlist ( ); /构造函数 GenList ( );/析构函数 GenList

11、Node& Head ( ); /返回表头元素 GenList& Tail ( ); /返回表尾 GenListNode *First ( ); /返回第一个元素 GenListNode * Next ( GenListNode *elem ); /返回表元素elem的直接后继元素 void setNext ( GenListNode *elem1, GenListNode *elem2 ); /将elem2插到表中元素elem1后 void Copy ( const GenList & l ); /广义表的复制 int depth ( ); /计算一个非递归表的深度 int Createli

12、st ( GenListNode *ls, char * s );/从广义表的字符串描述 s 出发, /建立一个带表头结点的广义表结构 Items& GenListNode : Info ( GenListNode * elem ) /返回表元素elem的值 Items *pitem = new Items; pitem-utype = elem-utype; pitem-value = elem-value; return * pitem;GenListNode& GenListNode :setInfo ( Items &x ) /修改表元素的值为 x utype = x-utype; v

13、alue = x-value; Genlist : GenList ( ) /构造函数 GenListNode *first = new GenListNode( ); first-utype = 0; first-ref = 1; first-tlink = NULL;Items& GenList : Head ( ) /若广义表非空，则返回其第一个元素的值，/否则函数没有定义。 if ( first-tlink = NULL ) return NULL; else /非空表 Items * temp = new Items; temp-utype = frist-tlink-utype;

14、temp-value = frist-tlink-value; return * temp; /返回类型及值 GenList& GenList : Tail ( ) /若广义表非空，则返回广义表除第一个元/素外其它元素组成的表, 否则函数没有定义 if ( frist-tlink = NULL ) return NULL; else /非空表 GenList * temp; temp-first = Copy ( first ); return * temp; GenListNode * GenList : First ( ) if ( first-tlink = NULL ) return

15、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& ls ) first = Copy ( ls.first );/共有函数GenListNode* GenList : Copy ( GenListNode* ls ) /私有函数 GenListNode *q = NULL; if ( ls

16、!= NULL ) q = new GenListNode ( ls-utype, NULL ); switch ( ls-utype ) 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); retur

17、n q;求广义表的深度求广义表的深度1111234int GenList : depth ( GenListNode *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 dep

18、th ( first );0 11 5331 2 0 12 x 0 10 12 y32 x void delvalue(GenListNode * ls, const value x) /在广义表中删除所有含 x 的结点 if ( ls-tlink != NULL ) /非空表 GenListNode * p = ls-tlink; while ( p != NULL & /横扫链表 ( ( p-utype = 1 & p-value.intinfo = x ) | ( p-utype = 2 & p-value.charinfo = x ) ) ls-tlink = p-tlink; del

19、ete p; /删除 p = ls-tlink; /指向同一层后继结点 if ( p != NULL ) if ( p-utype = 3 ) /在子表中删除 delvalue ( p-value.hlink, x ); 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;