C语言程序设计
尹宝林
第四讲：递归
递归的概念和作用
?概念或函数直接或间接引用自身?
在可计算性理论中有重要的地位
?
递归可枚举
?
常用的重要机制
?概念的表达
?数据结构和算法的描述?
重要的思维方式
?
现代程序设计语言中都提供支持
2005-1-2
C语言程序设计进阶
2
递归概念的例
?
?
树
树的非递归定义
?
连通且无圈的无向图
一个节点是一棵树
一棵树的每个节点可以有m个分支，其中每一个分支都是一棵树
一棵树中的任意两个节点间只有一条通路
?
树的递归定义
1.2.
3.
2005-1-2C语言程序设计进阶3
递归算法的例
?
排序
?
归并排序(merge sort)
?
最典型常用的实现方法是通过递归的定义?
快速排序算法(quick sort)
?
直接通过递归定义
2005-1-2C语言程序设计进阶4
