C 语言程序设计 尹宝林

递归过程描述的基本思想

???

把问题化为形式相同但规模较小的问题在问题规模缩小到一定的程度时加以解决递归的描述

????

定义对问题可以直接求解的情况和方法用自引用的方式描述问题的一般求解过程在对自身的引用过程中降低问题的复杂度在复杂度降低到一定程度时直接求解

C语言程序设计进阶

13

2005-1-2

递归过程描述的基本思想(续)

?与数学归纳法类似?

数学归纳法

在证明一个关于整数的公式时1.证明该公式对一个整数k成立2.假设该公式对某一整数n成立3.证明该公式对整数n+1成立

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

递归过程的描述步骤

1.2.

?

确定递归参数

定义递归的终止条件和基础计算

当递归参数为一个确定的值时应当如何直接进行计算

3.

?

定义递归调用

当递归参数不满足终止条件时，将计算表示为包含对自身调用的计算

对自身调用时递归参数应更接近终止条件

C语言程序设计进阶

15

?

2005-1-2

递归过程描述的例

?

阶乘

0! = 1

n! = n * (n –1)!

?

组合公式

C1m= mCmm= 1

Cn= Cnn-1m

m-1 +Cm-1

2005-1-2

C语言程序设计进阶

16