第五章 递归与广义表 递归的概念 递归过程与递归工作栈 递归与回溯 广义表.

Presentation on theme: "第五章 递归与广义表 递归的概念 递归过程与递归工作栈 递归与回溯 广义表."— Presentation transcript:

1 第五章 递归与广义表 递归的概念 递归过程与递归工作栈 递归与回溯 广义表

2 递归的概念 递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 以下三种情况常常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的

3 定义是递归的 例如，阶乘函数 求解阶乘函数的递归算法 long Factorial ( long n ) {
if ( n == 0 ) return 1; else return n * Factorial (n-1); }

4 求解阶乘 n! 的过程 主程序 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

5 数据结构是递归的 一个结点，它的指针域为NULL，是一个单链表; 一个结点，它的指针域指向单链表，仍是一个单链表。 例如，单链表结构 f f
 f  f 一个结点，它的指针域为NULL，是一个单链表; 一个结点，它的指针域指向单链表，仍是一个单链表。

6 搜索链表最后一个结点并打印其数值 template <class Type>
void Print ( ListNode<Type> *f ) { if ( f ->link == NULL ) cout << f ->data << endl; else Print ( f ->link ); } 递归找链尾 a0 a1 a2 a3 a4 f  f f f f

7 在链表中寻找等于给定值的结点并打印其数值 template <class Type> void Print ( ListNode<Type> *f, Type& x ) { if ( f != NULL ) if ( f -> data == x ) cout << f -> data << endl; else Print ( f -> link, x ); } 递归找含x值的结点 f x  f f f

8 问题的解法是递归的 例如，汉诺塔(Tower of Hanoi)问题的解法：
如果 n = 1，则将这一个盘子直接从 A 柱移到 C 柱上。否则，执行以下三步： ① 用 C 柱做过渡，将 A 柱上的 (n-1) 个盘子移到 B 柱上： ② 将 A 柱上最后一个盘子直接移到 C 柱上； ③ 用 A 柱做过渡，将 B 柱上的 (n-1) 个盘子移到 C 柱上。

9

10 #include <iostream.h>
#include "strclass.h” void Hanoi (int n, String A, String B, String C) { //解决汉诺塔问题的算法 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 ); }

11 递归过程与递归工作栈 递归过程在实现时，需要自己调用自己。 层层向下递归，退出时的次序正好相反： 递归调用
n! (n-1)! (n-2)! ! !=1 返回次序 主程序第一次调用递归过程为外部调用； 递归过程每次递归调用自己为内部调用。 它们返回调用它的过程的地址不同。

12 递归工作栈 每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。
每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。 局部变量 返回地址 参 数 活动记录框架 递归 工作记录

13 函数递归时的活动记录 调用块 函数块 ………………. <下一条指令> Function(<参数表>) ……………….
<return> 函数块 返回地址(下一条指令) 局部变量 参数

14 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 }

15 计算Fact时活动记录的内容 递归调用序列 参数 返回地址 返回时的指令 RetLoc1 return 4*6 //返回24
参数 返回地址 返回时的指令 RetLoc1 return 4*6 //返回24 4 RetLoc1 递归调用序列 RetLoc2 return 3*2 //返回6 3 RetLoc2 2 RetLoc2 RetLoc2 return 2*1 //返回2 1 RetLoc2 RetLoc2 return 1*1 //返回1 0 RetLoc2 RetLoc2 return //返回1

16 递归过程改为非递归过程 递归过程简洁、易编、易懂 递归过程效率低，重复计算多 改为非递归过程的目的是提高效率
单向递归和尾递归可直接用迭代实现其非递归过程 其他情形必须借助栈实现非递归过程

17 计算斐波那契数列的函数Fib(n)的定义
如 F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5 求解斐波那契数列的递归算法 long Fib ( long n ) { if ( n <= 1 ) return n; else return Fib (n-1) + Fib (n-2); }

18 调用次数 NumCall(k) = 2*Fib(k+1) - 1。
斐波那契数列的递归调用树 调用次数 NumCall(k) = 2*Fib(k+1) - 1。

19          栈结点 n tag tag = 1, 向左递归；tag = 2, 向右递归 Fib(4) Fib(3)

20                            Fib(4) Fib(3)
2 1 3 1 4 1 2 2 3 1 4 1    3 1 4 1  3 2 4 1      4 1  4 2       n=1 sum=0+1 n=0 sum=1+0 n=1 sum=1+1 n=2-2 n=3-2 n=4-2

21                  Fib(4) Fib(3) Fib(2) Fib(2) Fib(1)
2 1 4 2  2 2 4 2    4 2    n=1 sum=2+1 n=0 sum=3+0 n=2-2

22 long Fibnacci ( long n ) {
Stack<Node> S; Node *w; long sum = 0; //反复执行直到所有终端结点数据累加完 do { while ( n > 1 ) { w->n = n; w->tag = 1; S.push ( w ); n--; } //向左递归到底, 边走边进栈 sum = sum + n; //执行求和

23 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;

24 单向递归用迭代法实现 long FibIter ( long n ) { if ( n <= 1 ) return n;
long twoback = 0, oneback = 1, Current; for ( int i = 2; i <= n; i++ ) { Current = twoback + oneback; twoback = oneback; oneback = Current; } return Current;

25 尾递归用迭代法实现 void recfunc ( int A[ ], int n ) { if ( n >= 0 ) {
void recfunc ( int A[ ], int n ) { if ( n >= 0 ) { cout << A[n] << “ ”; n--; recfunc ( A, n ); }

26 void sterfunc ( int A[ ], int n ) {
//消除了尾递归的非递归函数 while ( n >= 0 ) { cout << "value " << A[n] << endl; n--; }

27 递归与回溯 常用于搜索过程 n皇后问题 在 n 行 n 列的国际象棋棋盘上，若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相攻击。n皇后问题是指找到这 n 个皇后的互不攻击的布局。

28     k = i+j k = n+i-j-1 0#次对角线 2#次对角线 1#次对角线 4#次对角线 3#次对角线 0 1 2 3
6#次对角线 k = i+j 1#次对角线 3#次对角线 5#次对角线 1 2 3    0#主对角线 2#主对角线 4#主对角线 6#主对角线 1#主对角线 3#主对角线 5#主对角线  k = n+i-j-1

29 解题思路 安放第 i 行皇后时，需要在列的方向从 0 到 n-1 试探 ( j = 0, …, n-1 ) 在第 j 列安放一个皇后：
如果没有出现攻击，在第 j 列安放的皇后不动，递归安放第 i+1行皇后。

30 col [n] ：col[i] 标识第 i 列是否安放了皇后
设置 4 个数组 col [n] ：col[i] 标识第 i 列是否安放了皇后 md[2n-1] : md[k] 标识第 k 条主对角线是否安放了皇后 sd[2n-1] : sd[k] 标识第 k 条次对角线是否安放了皇后 q[n] : q[i] 记录第 i 行皇后在第几列

31 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 列的皇后；

32 算法求精 void Queen( int i ) { for ( int j = 0; j < n; j++ ) {
if ( !col[j] && !md[n+i-j-1] && !sd[i+j] ) { /*第 i 行第 j 列没有攻击 */ col[j] = md[n+i-j-1] = sd[i+j] = 1; q[i] = j; /*在第 i 行第 j 列安放皇后*/

33 cout << q[j] << ‘,’; cout << endl; }
if ( i == n-1 ) { /*输出一个布局*/ for ( j = 0; j < n; j++ ) cout << q[j] << ‘,’; cout << endl; } else Queen ( i+1 ); col[j] = md[n+i-j-1] = sd[i+j] = 0; q[i] = 0; /*撤消第 i 行第 j 列的皇后*/

34 广义表 (General Lists ) 限序列，记作 LS = (a0, a1, a2, …, an-1)
LS是表名，ai是表元素，它可以是表 (称 为子表)，可以是数据元素(称为原子)。 n为表的长度。n = 0 的广义表为空表。 n > 0时，表的第一个表元素称为广义表 的表头(head)，除此之外，其它表元素组 成的表称为广义表的表尾(tail)。

35 广义表的特性 有次序性 有长度 有深度 可共享 可递归 A = ( ) B = ( 6, 2 )
C = ( ‘a’, ( 5, 3, ‘x’ ) ) D = ( B, C, A ) E = ( B, D ) F = ( 4, F )

36

37 广义表的表示  5 12 ‘s’ 47 ‘a’ 只包括整数和字符型数据的广义表链表表示  5 2 6 3 10    3 2 4
list1 5 12 ‘s’ 47 ‘a’ 只包括整数和字符型数据的广义表链表表示  list2 5 2 6 3 10    3 2 4 14 9 3  表中套表情形下的广义表链表表示

38 广义表结点定义 utype value tlink
值value utype=0时, 存放引用计数(ref)；utype=1时, 存放整数值(intinfo)；utype=2时, 存放字符型数据(charinfo)；utype=3时, 存放指向子表表头的指针(hlink) 尾指针tlink utype=0时, 指向该表第一个结点；utype0时, 指向同一层下一个结点

39 广义表的存储表示 A  0 1 B  0 1 1 6 1 2 B C A D  0 1 3 3 3  C 0 1 2 ‘a’ 3 
0 1 B  0 1 1 6 1 2 B C A D  0 1 3 3 3  C 0 1 2 ‘a’ 3  0 1 1 5 1 3 2 ‘x’ B D  E 0 1 3 3  F 0 1 1 4 3

40 广义表的类定义 class GenList; //GenList类的前视声明
class GenListNode { //广义表结点类的前视声明 struct Items { //仅有结点信息的项 friend class GenlistNode; friend class Genlist; int utype; //＝0 / 1 / 2 / 3 union { //联合

41 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

42 GenListNode * tlink; //下一结点指针
union { //联合 int ref; //utype=0, 存放引用计数 int intinfo; //utype=1, 存放整数值 char charinfo; //utype=2, 存放字符 GenListNode *hlink; //utype =3, 存放指向子表的指针 } value; public: GenListNode ( ) : utype (0), tlink (NULL), ref (0) { } //构造函数, 建表头结点

43 GenListNode ( int t, GenListNode *next =
NULL ) { } //构造函数：建表结点 Items& Info ( GenListNode *elem ); //返回表元素elem的值 int nodetype ( GenListNode *elem ) { return elem->utype; } //返回表元素elem的数据类型 GenListNode& setInfo ( Items&x ); //将表元素elem中的值修改为x };

44 class GenList { //广义表类定义
private: GenListNode *first; //广义表头指针 GenListNode *Copy ( GenListNode *ls ); //复制一个 ls 指示的无共享非递归表 int depth ( GenListNode *ls ); //计算由 ls 指示的非递归表的深度 int equal (GenListNode *s, GenListNode *t); //比较以s和t为表头的两个表是否相等 void Remove (GenListNode *ls ); //释放以 ls 为表头结点的广义表

45 public: Genlist ( ); //构造函数 ~GenList ( ); //析构函数 GenListNode& Head ( ); //返回表头元素 GenList& Tail ( ); //返回表尾 GenListNode *First ( ); //返回第一个元素 GenListNode * Next ( GenListNode *elem ); //返回表元素elem的直接后继元素 void setNext ( GenListNode *elem1, GenListNode *elem2 ); //将elem2插到表中元素elem1后

46 void Copy ( const GenList & l );
//广义表的复制 int depth ( ); //计算一个非递归表的深度 int Createlist ( GenListNode *ls, char * s ); //从广义表的字符串描述 s 出发, //建立一个带表头结点的广义表结构 }

47 广义表的访问算法 广义表结点类的存取成员函数 Items& GenListNode ::
Info ( GenListNode * elem ) { //返回表元素elem的值 Items *pitem = new Items; pitem->utype = elem->utype; pitem->value = elem->value; return * pitem; }

48 GenListNode& GenListNode ::
setInfo ( Items &x ) { //修改表元素的值为 x utype = x->utype; value = x->value; } 广义表类的构造和访问成员函数 Genlist :: GenList ( ) { //构造函数 GenListNode *first = new GenListNode( ); first->utype = 0; first->ref = 1; first->tlink = NULL;

49 Items& GenList :: Head ( ) {
//若广义表非空，则返回其第一个元素的值， //否则函数没有定义。 if ( first->tlink == NULL ) return NULL; else { //非空表 Items * temp = new Items; temp->utype = frist->tlink->utype; temp->value = frist->tlink->value; return * temp; //返回类型及值 }

50 GenList& GenList :: Tail ( ) {
//若广义表非空，则返回广义表除第一个元 //素外其它元素组成的表, 否则函数没有定义 if ( frist->tlink == NULL ) return NULL; else { //非空表 GenList * temp; temp->first = Copy ( first ); return * temp; }

51 GenListNode * GenList ::
First ( ) { if ( first->tlink == NULL ) return NULL; else return first->tlink; } Next ( GenListNode *elem ) { if ( elem->tlink == NULL ) return NULL; else return elem->tlink;

52 广义表的递归算法 广义表的复制算法 void GenList :: Copy ( const GenList& ls ) {
first = Copy ( ls.first ); //共有函数 } GenListNode* GenList :: Copy ( GenListNode * ls ) { //私有函数 GenListNode *q = NULL; if ( ls != NULL ) { q = new GenListNode ( ls->utype, NULL );

53 switch ( ls->utype ) {
case 0: q->value.ref = ls->value.ref; break; case 1: q->value.intgrinfo = ls->value.intgrinfo; case 2: q->value.charinfo = ls->value.charinfo; case 3: q->value.hlink = Copy (ls->value.hlink); }

54 q->tlink = Copy (ls->tlink);
} return q;   

55 求广义表的深度 例如，对于广义表 E (B (a, b), D (B (a, b), C (u, (x, y, z)), A ( ) ) )
1 1 1 1 2 3 4

56 int 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 < n ) m = n; //m记最大深度 } temp = temp->tlink; return m+1;

57 广义表的删除算法 int GenList :: depth ( ) { return depth ( first ); } ls 扫描子链表
 0 1 1 5 3 3 1 2   0 1 2 ‘x’ 2 ‘y’ 0 1 3  扫描子链表 若结点数据为‘x’, 删除。可能做循环连续删。 若结点数据不为‘x’，不执行删除。 若结点为子表，递归在子表执行删除。 0 1 2 ‘x’

58 扫描子链表 若结点数据为‘x’, 删除。可能做循环连 续删。 若结点数据不为‘x’，不执行删除。 若结点为子表，递归在子表执行删除。 void delvalue(GenListNode * ls, const value x) { //在广义表中删除所有含 x 的结点 if ( ls->tlink != NULL ) { //非空表 GenListNode * p = ls->tlink;

59 while ( p != NULL && //横扫链表
( ( p->utype == 1 && p->value.intinfo == x ) || ( p->utype == 2 && p->value.charinfo == x ) ) { ls->tlink = p->tlink; delete p; //删除 p = ls->tlink; //指向同一层后继结点 } if ( p != NULL ) { if ( p->utype == 3 ) //在子表中删除 delvalue ( p->value.hlink, x );

60 delvalue ( p, x ); //在后续链表中删除
} GenList :: ~GenList ( ) { //析构函数 Remove ( first ); void GenList :: Remove ( GenListNode *ls ) { //私有函数：释放以 ls 为表头指针的广义表 ls->value.ref --; //引用计数减1

61 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; }