5.5　递归

递归就是在程序开发过程中，函数调用自己的一种编程思路。使用递归编写代码可以大量减少程序的代码量，但是会提高系统资源的占用率。C++语言也支持递归。本节将详细讲解递归的相关内容。

5.5.1　什么是递归

递归来源于英文recursion，可以翻译为递推、递归。递归就是将复杂的问题，按照特定规律，逐步简化的一个过程。递归由递推、终止条件、回溯及递归方式四部分组成。

❑ 递推：将复杂数据进行简化的过程。

❑ 终止条件：递推过程的终止界限。

❑ 回溯：将简化的所有数据进行回推的过程。

❑ 递归方式：递推与回溯过程中都需要遵循的简化数据和回推数据的规律。

下面以计算4！（4的阶乘）的值为例进一步讲解递归的思路。按照数学的解题思路，我们会将4！转换为一个等式，然后计算4！的值，如下所示。

从数学解题思路中可以发现如下规律。

如果使用变量n来代替数字，则可以转换为：

所以，递归方式应该为n！=n*（n-1）！。而数据递归的终止条件是n=1。找到了递归方式与终止条件，下面对4！进行递归处理。

首先，对数据进行递推简化处理。

❑ 第1次递推，将4！拆分为4*3！。此时4为最简单数据，3！为复杂数据。

❑ 第2次递推，将3！拆分为3*2！，此时3为简单数据，2！为复杂数据。

❑ 第3次递推，将2！拆分为2*1！，此时2为简单数据，1！为复杂数据。

❑ 第4次递推，将1！拆分为1*1，1为最简单数据，符合终止递推过程的条件。

然后，开始回溯处理。

❑ 运算结果为1*1=1，将1向上第1次回溯。

❑ 替换后为2*1=2，将2向上第2次回溯。

❑ 替换后为3*2=6，将6向上第3次回溯。

❑ 替换后为4*6=24，此时，递归完成，计算出4！的值为24。

整个过程就是递归。为了更好地理解，我们用图5.8展示递归的过程。

5.5.2　递归的实现

C++语言使用递归是通过函数反复调用自身来实现的，这样做会大量节省代码，但是会增加运算量。其语法形式如下。

其中，递归方式由调用自身的函数为基础组成，递推从调用自身的函数开始，回溯从终止条件的return语句开始。

【示例5-8】下面演示计算10的阶乘的值。

程序运行结果如下。

计算10的阶乘的递归过程如图5.9所示。

递归过程简单说就是一种化繁为简的过程，在编程语言中十分常见。一般而言，递归函数过程对于计算阶乘、级数、指数运算有特殊效果。