4.2　递归

4.2.1　递归的原理

递归是指函数直接或间接地重复调用自身的过程。在处理某些问题时，递归可以显著地降低难度，例如二叉树的前序、中序、后序遍历，汉诺塔问题等。

实质上，递归的原理类似于数学归纳法，证明分两个步骤：

（1）证明当n=1时命题成立。

（2）证明如果在n=m时命题成立，那么可以推导出在n=m+1时命题也成立。（m代表任意自然数）

递归处理问题也有两个基本要素：

●　起始条件或退出条件。

●　问题分解为子问题。

我们来看一个基础的阶乘的递归实现示例，程序代码如下：（源码文件：ch04/fact.php）

第4至6行是退出条件，即0!=1，1!=1。

第7行，将阶乘问题分解，即

fact(10) = 10* fact(9)
fact(9) = 9 * fact(8)
…
fact(2) = 2 * fact(1) = 2 * 1

依次调用即得到最后的结果。

4.2.2　递归的优缺点

1．递归的优点

●　将复杂问题分解为简单问题，易于理解。

●　实现简单，某些问题转换为迭代之后实现方极其复杂（如汉诺塔问题），但使用递归实现就要简单很多。

2．递归的缺点

●　函数调用次数多，效率低。

●　空间浪费较多。

●　可能存在多余的调用。

●　递归层级过深造成堆栈的溢出。

递归的优点和缺点，使得科学家们对其“又爱又恨”，为了扬长避短，科学家们利用动态规划缓解递归的某些缺点。关于动态规划的实现我们在第12章第7节将会详细描述。

4.2.3　面试题：用递归实现斐波那契数列

斐波那契数列（Fibonacci Sequence）的第1项和第2项为1，从第3项开始，每一项都是前两项之和：

1  1  2  3  5  8  13  21...

程序实现如下：（源码文件：ch04/fibonacci.php）

4.2.4　面试题：二叉树的中序遍历

题目描述：利用递归实现二叉树的中序遍历。

解答：二叉树的中序遍历，是按照左子树→根结点→右子树的顺序访问二叉树的所有结点。访问的操作包括操作结点的值、更改结点的值等。

示例代码如下：（源码文件：ch04/tree.php）