c语言(递归).ppt

C语言程序设计尹宝林
第四讲:递归
2005-1-2
1
C语言程序设计进阶
递归的概念和作用
概念或函数直接或间接引用自身
在可计算性理论中有重要的地位
递归可枚举
常用的重要机制
概念的表达
数据结构和算法的描述
重要的思维方式
现代程序设计语言中都提供支持
2005-1-2
2
C语言程序设计进阶
递归概念的例
树
树的非递归定义
连通且无圈的无向图
树的递归定义
一个节点是一棵树
一棵树的每个节点可以有m个分支,其中每一个分支都是一棵树
一棵树中的任意两个节点间只有一条通路
2005-1-2
3
C语言程序设计进阶
递归算法的例
排序
归并排序(merge sort)
最典型常用的实现方法是通过递归的定义
快速排序算法(quick sort)
直接通过递归定义
2005-1-2
4
C语言程序设计进阶
递归函数的例
直接引用的递归函数:对树的中序遍历
typedef struct t_node {
int value;
struct t_node *l_tree, *r_tree;
} t_node;
void treat_tree(t_node *treep, void (*op_func)(int))
{
if (treep == NULL)
return;
treat_tree(treep->l_tree, op_func);
op_func(treep->value);
treat_tree(treep->r_tree, op_func);
}
2005-1-2
5
C语言程序设计进阶
递归函数的例(续)
间接引用的递归函数
void a(int i)
{
……
b(i – 1);
}
void b(int i)
{
……
a(i);
}
2005-1-2
6
C语言程序设计进阶
递归函数的例(续)
递归曲线
Hilbert曲线
Sierpinski曲线
分形(fractal)
2005-1-2
7
C语言程序设计进阶
递归在程序设计中的例
程序设计语言的语法描述
Backus-Naur Form (巴克斯范式)
Algol、C、……
数据结构
控件
复杂的嵌套结构
……
2005-1-2
8
C语言程序设计进阶
递归的优点
概念清晰,易于理解
描述简单,易于实现
例:GUI中的嵌套的选单(Menu)
代码紧凑,易于维护
2005-1-2
9
C语言程序设计进阶
递归函数的缺点
在某些情况下计算复杂度较高
不适当的定义引起的重复计算
在某些情况下占用存储空间较多
深度递归调用引起的资源消耗
函数调用的开销
计算过程简单时函数调用开销的比例增加
2005-1-2
10
C语言程序设计进阶