? 递归的概念
? 递归过程与递归工作栈
? 递归与回溯
? 广义表
递归的概念
? 递归的定义 若一个对象部分地包含它
自己,或用它自己给自己定义,则称这
个对象是递归的；若一个过程 直接地或
间接地调用自己,则称这个过程是递归
的过程。
? 以下三种情况常常用到递归方法。
? 定义是递归的
? 数据结构是递归的
? 问题的解法是递归的
定义是递归的
求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n * Factorial (n-1);
}
例如，阶乘函数
?
?
?
???
?
?
时当
时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘 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 ?
搜索链表最后一个结点并打印其数值
template <class Type>
void Print ( ListNode<Type> *f ) {
if ( f ->link == NULL )
cout << f ->data << endl;
else Print ( f ->link );
}
f
f f f f
?a0 a1 a2 a3 a4
递归找链尾
在链表中寻找等于给定值的结点并打印
其数值
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 );
}
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 <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时活动记录的内容
递
归
调
用
序
列
0 RetLoc2
1 RetLoc2
2 RetLoc2
3 RetLoc2
4 RetLoc1
参数 返回地址 返回时的指令
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-2);
}
?
?
?
????
?
?
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
如 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) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
? ?
? ?
?
?
?
?
?
2 1
3 1
4 1
n=1
sum=0+1
2 2
3 1
4 1
n=2-2
3 1
4 1
n=0
sum=1+0
3 2
4 1
n=3-2? ? ? ?
4 1
n=1
sum=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 1
4 2
n=1
sum=2+1
2 2
4 2
n=2-2
4 2
n=0
sum=3+0
?
? ? ?
?
?
? ?
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 ) {
cout << A[n] <<,,;
n--;
recfunc ( A,n );
}
}
25 36 72 18 99 49 54 63
尾递归用迭代法实现
void sterfunc ( int A[ ],int n ) {
//消除了尾递归的非递归函数
while ( n >= 0 ) {
cout << "value " << A[n] << endl;
n--;
}
}
递归与回溯 常用于搜索过程
n皇后问题
在 n 行 n 列的 国际象棋棋盘上，
若 两个皇后 位于 同一行, 同一列,
同一对角线 上，则称为它们为 互相
攻击 。 n皇后问题是指 找到这 n 个
皇后的互不攻击的布局 。
1#主对角线
3#主对角线
5#主对角线
?
?
?
0#次对角线
2#次对角线
4#次对角线
6#次对角线
1#次对角线
3#次对角线
5#次对角线
0#主对角线
2#主对角线
4#主对角线
6#主对角线
?
0 1 2 3
0
1
2
3
k = i+j
k = n+i-j-1
解题思路
? 安放 第 i 行 皇后时，需要在列的方向从 0
到 n-1 试探 ( j = 0,…,n -1 )
? 在 第 j 列 安放一个皇后：
? 如果在 列, 主对角线, 次对角线 方向
有其它皇后，则出现攻击，撤消在 第 j
列 安放的皇后。
? 如果没有出现攻击，在 第 j 列 安放的
皇后不动，递归安放第 i+1行皇后。
? 设置 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 列安放皇后 */
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 )
?广义表的概念 n ( ? 0 )个表元素组成的有
限序列,记作
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 2
3 2 4
36 10
3914
?
?
?
?
?list2
5list1 ?12 47 ‘a’‘s’
广义表结点定义
? 结点类型 utype = 0,表头； = 1,整型原子；
= 2,字符型原子； = 3,子表
? 值 value utype=0时,存放引用计数 (ref)；
utype=1时,存放整数值 (intinfo)； utype=2
时,存放字符型数据 (charinfo)； utype=3时,
存放指向子表表头的指针 (hlink)
? 尾指针 tlink utype=0时,指向该表第一个
结点； utype?0时,指向同一层下一个结点
utype value tlink
广义表的存储表示
E
B
F 0 1 1 4 3
0 1 33
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 1A ?
广义表的类定义
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;
}
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 != 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);
}
return q;
}
?
?
?
求广义表的深度
?
?
?
??
?
?
??
?
???
1) },{ D e p t h ( am a x1
LS,0
LS,1
)D e p t h ( L S
i
1ni0
n，其它
为原子时当
为空表时当
例如，对于广义表
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 );
}
广义表的删除算法
0 1 1 5 3 3 1 2 ?
0 1 2 ‘x’ ?
0 1
0 12 ‘y’
ls
3
2 ‘x’
?
?? 扫描子链表
? 若结点数据为‘ x’,删除。可能做循环连续删。
? 若结点数据不为‘ 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;
}
}
}
? 递归过程与递归工作栈
? 递归与回溯
? 广义表
递归的概念
? 递归的定义 若一个对象部分地包含它
自己,或用它自己给自己定义,则称这
个对象是递归的；若一个过程 直接地或
间接地调用自己,则称这个过程是递归
的过程。
? 以下三种情况常常用到递归方法。
? 定义是递归的
? 数据结构是递归的
? 问题的解法是递归的
定义是递归的
求解阶乘函数的递归算法
long Factorial ( long n ) {
if ( n == 0 ) return 1;
else return n * Factorial (n-1);
}
例如，阶乘函数
?
?
?
???
?
?
时当
时当
1,)!1(
0,1
!
n
n
nn
n
求解阶乘 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 ?
搜索链表最后一个结点并打印其数值
template <class Type>
void Print ( ListNode<Type> *f ) {
if ( f ->link == NULL )
cout << f ->data << endl;
else Print ( f ->link );
}
f
f f f f
?a0 a1 a2 a3 a4
递归找链尾
在链表中寻找等于给定值的结点并打印
其数值
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 );
}
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 <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时活动记录的内容
递
归
调
用
序
列
0 RetLoc2
1 RetLoc2
2 RetLoc2
3 RetLoc2
4 RetLoc1
参数 返回地址 返回时的指令
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-2);
}
?
?
?
????
?
?
1n2 ),F i b ( n1)F i b ( n
0,1nn,
)F i b ( n
如 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) Fib(1) Fib(0)
Fib(2)
Fib(1)
Fib(3)
Fib(4)
? ?
? ?
?
?
?
?
?
2 1
3 1
4 1
n=1
sum=0+1
2 2
3 1
4 1
n=2-2
3 1
4 1
n=0
sum=1+0
3 2
4 1
n=3-2? ? ? ?
4 1
n=1
sum=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 1
4 2
n=1
sum=2+1
2 2
4 2
n=2-2
4 2
n=0
sum=3+0
?
? ? ?
?
?
? ?
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 ) {
cout << A[n] <<,,;
n--;
recfunc ( A,n );
}
}
25 36 72 18 99 49 54 63
尾递归用迭代法实现
void sterfunc ( int A[ ],int n ) {
//消除了尾递归的非递归函数
while ( n >= 0 ) {
cout << "value " << A[n] << endl;
n--;
}
}
递归与回溯 常用于搜索过程
n皇后问题
在 n 行 n 列的 国际象棋棋盘上，
若 两个皇后 位于 同一行, 同一列,
同一对角线 上，则称为它们为 互相
攻击 。 n皇后问题是指 找到这 n 个
皇后的互不攻击的布局 。
1#主对角线
3#主对角线
5#主对角线
?
?
?
0#次对角线
2#次对角线
4#次对角线
6#次对角线
1#次对角线
3#次对角线
5#次对角线
0#主对角线
2#主对角线
4#主对角线
6#主对角线
?
0 1 2 3
0
1
2
3
k = i+j
k = n+i-j-1
解题思路
? 安放 第 i 行 皇后时，需要在列的方向从 0
到 n-1 试探 ( j = 0,…,n -1 )
? 在 第 j 列 安放一个皇后：
? 如果在 列, 主对角线, 次对角线 方向
有其它皇后，则出现攻击，撤消在 第 j
列 安放的皇后。
? 如果没有出现攻击，在 第 j 列 安放的
皇后不动，递归安放第 i+1行皇后。
? 设置 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 列安放皇后 */
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 )
?广义表的概念 n ( ? 0 )个表元素组成的有
限序列,记作
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 2
3 2 4
36 10
3914
?
?
?
?
?list2
5list1 ?12 47 ‘a’‘s’
广义表结点定义
? 结点类型 utype = 0,表头； = 1,整型原子；
= 2,字符型原子； = 3,子表
? 值 value utype=0时,存放引用计数 (ref)；
utype=1时,存放整数值 (intinfo)； utype=2
时,存放字符型数据 (charinfo)； utype=3时,
存放指向子表表头的指针 (hlink)
? 尾指针 tlink utype=0时,指向该表第一个
结点； utype?0时,指向同一层下一个结点
utype value tlink
广义表的存储表示
E
B
F 0 1 1 4 3
0 1 33
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 1A ?
广义表的类定义
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;
}
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 != 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);
}
return q;
}
?
?
?
求广义表的深度
?
?
?
??
?
?
??
?
???
1) },{ D e p t h ( am a x1
LS,0
LS,1
)D e p t h ( L S
i
1ni0
n，其它
为原子时当
为空表时当
例如，对于广义表
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 );
}
广义表的删除算法
0 1 1 5 3 3 1 2 ?
0 1 2 ‘x’ ?
0 1
0 12 ‘y’
ls
3
2 ‘x’
?
?? 扫描子链表
? 若结点数据为‘ x’,删除。可能做循环连续删。
? 若结点数据不为‘ 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;
}
}
}
