8.8　递归

简单地说，当方法直接或者间接调用自己时，则发生了递归。

递归是一种算法，指的是方法在调用过程中直接或间接调用自身而产生的重入现象。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。

一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

注意：

❑递归就是在方法里调用自身；

❑在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口，否则将无限进行下去（死锁）。

我们已经知道了什么是递归，接下来，我们使用一个实例来说明有趣的递归算法。计算阶乘是递归程序设计的一个经典示例。计算某个数的阶乘就是用那个数去乘以包括1在内的所有比它小的数。例如，factorial（5）等价于54321，而factorial（3）等价于321。

阶乘的一个有趣特性是，某个数的阶乘等于起始数（starting number）乘以比它小1的数的阶乘。例如，factorial（5）与5*factorial（4）相同。你很可能会这样编写阶乘函数，见代码清单8-16：

代码清单8-16　阶乘计算

public int factorial（int n）

{

return n*factorial（n-1）；

}

能否看出这个程序有什么问题？对了，它缺少递归结束条件，这段程序将永远无休止地执行下去。因此，我们需要设置一个结束条件，如代码清单8-17所示：

代码清单8-17　改进后的阶乘计算

public int factorial（int n）

{

if（n==1）//递归结束条件

{

return 1；

}

else

{

return n*factorial（n-1）；

}

}

当然，任何事物都不是完美无瑕的，递归也有缺点：

❑运行效率较低；

❑在递归调用的过程当中，系统会为每一次调用生成新的栈帧，并使用栈来存储，因此递归次数过多容易造成栈溢出。