3.4　递归算法思想

递归算法是很常用的算法思想。使用递归算法，往往可以简化代码编写，提高程序的可读性。但是，不合适的递归往往导致程序的执行效率变低。

3.4.1　递归算法基本思想

递归算法即在程序中不断反复调用自身来达到求解问题的方法。此处的重点是调用自身，这就要求待求解的问题能够分解为相同问题的一个子问题。这样，通过多次递归调用，便可以完成求解。

递归调用是一个方法在其方法体内调用其自身的方法调用方式。这种方法也称为“递归方法”。在递归方法中，主调方法又是被调方法。执行递归方法将反复调用其自身。每调用一次就进入新的一层。

方法的递归调用分两种情况：直接递归和间接递归。

・直接递归，即在方法中调用方法本身。

・间接递归，即间接地调用一个方法，如func_a调用func_b，func_b又调用func_a。间接递归用得不多。

编写递归方法时，必须使用if语句强制方法在未执行递归调用前返回。如果不这样做，在调用方法后，它将永远不会返回。这是一个很容易犯的错误。

了解了递归方法的设计方法和工作原理后，即可对递归的优缺点进行以下总结。

在方法中使用递归的好处有：程序代码更简洁清晰，可读性更好。有的算法用递归表示要比用循环表示简洁精练，而且某些问题，特别是与人工智能有关的问题，更适宜用递归方法，如八皇后问题、汉诺塔问题等。有的算法，用递归能实现，而用循环却不一定能实现。

递归的缺点：大部分递归例程没有明显地减少代码规模和节省内存空间。递归形式比非递归形式运行速度要慢一些。这是因为附加的方法调用增加了时间开销，例如需要执行一系列的压栈出栈等操作。但在许多情况下，速度的差别不太明显。如果递归层次太深，还可能导致堆栈溢出。

3.4.2　递归算法实例

递归算法常用于一些数学计算，或者有明显的递推性质的问题。理解递归最常用的一个例子是编写程序求阶乘问题。

1.递归算法

所谓阶乘，就是从1到指定数之间的所有自然数相乘的结果，n的阶乘为：

n！=n*（n-1）*（n-2）*……*2*1

而对于（n-1）！，则有如下表达式：

（n-1）！=（n-1）*（n-2）*……*2*1

从上述两个表达式可以看到阶乘具有明显的递推性质，即符合如下递推公式：

n！=n*（n-1）！

因此，可以采用递归的思想来计算阶乘。递归算法计算阶乘的代码示例如下：

其中，输入参数n为需要计算的阶乘。在该方法中，当n<=1时，n！=1；当n>1时，通过递归调用来计算阶乘。方法fact是一个递归方法，在该方法内部，程序又调用了名为fact的方法（即自身）。方法的返回值便是n！。

2.递归算法计算阶乘

学习了前面的递归算法求解阶乘问题的算法，下面结合例子来分析一个阶乘运算的使用。完整的程序代码示例如下：

【程序3-3】

该程序中，首先由用户输入一个要求阶乘的整数，然后调用递归方法fact（）来计算阶乘。该程序的执行结果，如图3-3所示。

从上述内容可以看出，使用递归算法求解阶乘问题的代码比较简洁，易于理解。