4.1.5 递归函数

递归函数是指在一个函数体内直接或间接调用自己。

1.递归函数的概念

递归是一种描述问题和解决问题的基本方法。递归通常用来解决结构相似的问题。结构相似是指构成原问题的子问题与原问题在结构上相似，可以用类似的方法解决。

构成递归的必备条件有以下两个。

1）子问题与原问题是同样的问题，但是更简单。

2）不能无限制地调用本身，必须有一个化为非递归处理的出口。

以下3种情况常用到递归方法。

1）定义本身是递归的，如阶层的计算。

2）数据结构是递归的，如链表、树等。

3）问题的解法是递归的，如汉诺塔问题。

递归在算法描述中有着不可替代的作用。很多看似十分复杂的问题，使用递归算法来描述显得非常简洁与清晰。

2.追归函数定义

递归函数的优点是定义简单，逻辑清晰。典型的递归函数定义格式如下：

说明：

函数递归包含一种隐式的循环，它会重复执行某段代码，但这种重复执行无须循环控制，使用递归函数时需要注意防止溢出。在递归调用中，一个过程执行的某一步要用到它自身的上一步（或上几步）的结果。当一个函数不断地调用它自身时，必须在某个时刻函数的返回值是确定的，即不再调用它自身；否则，这种递归就变成了无穷递归，类似于死循环。因此，在定义递归函数时有一条重要规定：递归函数必须有出口，递归一定要向已知方向进行。

【例4-16】 利用递归函数计算n！。

分析：自然数n的阶乘可以递归定义为

使用递归算法求阶乘的过程为：输入n，如果n>0，则f=n*fact（n-1），否则f=1。

求阶乘的递归函数fact()的程序为：

调用函数的主程序为：

程序和运行结果如图4-5所示。

说明：

当n>0时，函数fact()调用自己，参数为n-1，该操作一直持续到n=1为止。

例如，当n=5时，求fact(5)的值，变为求5×fact(4)；求fact(4)的值又变为求4×fact(3)，依此类推，当n=0时，值为1，递归结束，其结果为5×4×3×2×1。如果把第1次调用fact()函数叫作0级调用，以后每调用一次级别增加1，过程参数n减1，则递归调用的过程如下。

【例4-17】 利用递归过程编写程序打印斐波那契（Fibonacci）数列。

1 1 2 3 5 8 13 21 34 55 …

分析：此数列的规律为它的头两个数为1，从第三个数开始其值是它前面的两个数之和。即

fibo(n)函数的程序为：

程序和运行结果如图4-6所示。