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

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

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

求解阶乘 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 返回 1

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

搜索链表最后一个结点并打印其数值 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

在链表中寻找等于给定值的结点并打印其数值 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

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

#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 ); }

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

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

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

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时活动记录的内容 递归调用序列 参数 返回地址 返回时的指令 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 //返回1

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

计算斐波那契数列的函数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); }

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

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

                           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

                 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

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; //执行求和

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 ( int i = 2; i <= n; i++ ) { Current = twoback + oneback; twoback = oneback; oneback = Current; } return Current;

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

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

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

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

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

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 行皇后在第几列

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 ( !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 列安放皇后*/

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 列的皇后*/

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

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

广义表的表示  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  表中套表情形下的广义表链表表示

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

广义表的存储表示 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

广义表的类定义 class GenList; //GenList类的前视声明 class GenListNode { //广义表结点类的前视声明 struct Items { //仅有结点信息的项 friend class GenlistNode; friend 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 intinfo; //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& Info ( GenListNode *elem ); //返回表元素elem的值 int nodetype ( GenListNode *elem ) { return elem->utype; } //返回表元素elem的数据类型 GenListNode& setInfo ( Items&x ); //将表元素elem中的值修改为x };

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 为表头结点的广义表

public: Genlist ( ); //构造函数 ~GenList ( ); //析构函数 GenListNode& 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 Createlist ( 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; value = 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; 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 NULL; else return first->tlink; } 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 != 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; case 2: q->value.charinfo = ls->value.charinfo; 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 ( 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;

广义表的删除算法 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’

扫描子链表 若结点数据为‘x’, 删除。可能做循环连 续删。 若结点数据不为‘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; delete 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; }