5 递归与广义表.ppt

文档介绍：递归的概念
递归过程与递归工作栈
递归与回溯
广义表
第五章递归与广义表
递归的概念
递归的定义若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的;若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。
以下三种情况常常用到递归方法。
定义是递归的
数据结构是递归的
问题的解法是递归的
定义是递归的
求解阶乘函数的递归算法
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

搜索链表最后一个结点并打印其数值
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 <>
#include "”
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 );
}
}