C 语言程序设计 尹宝林 - 图文

C语言程序设计

尹宝林

第四讲：递归

递归的概念和作用

?概念或函数直接或间接引用自身?

在可计算性理论中有重要的地位

?

递归可枚举

?

常用的重要机制

?概念的表达

?数据结构和算法的描述?

重要的思维方式

?

现代程序设计语言中都提供支持

2005-1-2

C语言程序设计进阶

2

递归概念的例

?

?

树

树的非递归定义

?

连通且无圈的无向图

一个节点是一棵树

一棵树的每个节点可以有m个分支，其中每一个分支都是一棵树

一棵树中的任意两个节点间只有一条通路

?

树的递归定义

1.2.

3.

2005-1-2C语言程序设计进阶3

递归算法的例

?

排序

?

归并排序(merge sort)

?

最典型常用的实现方法是通过递归的定义?

快速排序算法(quick sort)

?

直接通过递归定义

2005-1-2C语言程序设计进阶4