6.5　递归

    除了main（）函数外，C++函数可以调用自身，这称为递归，是一种通用的编程技术，可以有效降低问题的复杂度，为解决某些问题提供了极大的方便。首先来看一个用以求阶乘的函数，对于一个整数n，其阶乘n！定义为如下所示。

    n！=n（n-1）（n-2）……3210的阶乘为1，读者可以从阶乘定义中总结出以下规律，对n＞0而言有如下递归。 n！=n*（n-1）！直观上，可以用循环语句计算n的阶乘，如下列代码所示。 int Calc（int n） { int res=1； for（int i=1；i＜=n；i++） res*=I； return res； }

    但是，使用递归可以让函数代码更为清晰，代码6.12使用递归构造Calc（）函数，用以计算用户输入的整数的阶乘。

    代码6.12　计算某个整数的阶乘Factorial

    ＜—————————————文件名：example612.cpp——————————————＞ 01　#include＜iostream＞ 02　using namespace std； 03　int main（） 04　{ 05　int Calc（int）；//Calc（）函数声明 06　int x； 07　cout＜＜"请输入一个大于1的整数："＜＜endl； 08　cin＞＞x；//接收用户键盘输入 09　int y=Calc（x）；//函数调用，递归计算 10　cout＜＜x＜＜"的阶乘是"＜＜y＜＜endl； 11　return 0； 12　} 13　int Calc（int n）//定义计算阶乘的函数Calc（） 14　{ 15　if（n==1）//如果输入参数n为1，返回1 16　return 1； 17　else 18　return nCalc（n-1）；//否则，递归返回nCalc（n-1） 19　}

    输出结果如下所示。

    请输入一个大于1的整数： 4（注：键盘输入） 4的阶乘是24

    【代码解析】Calc（）函数用于计算参数n的阶乘，当n大于1，函数的返回值是“nCalc（n-1）；”，在代码第18行，Calc（）函数又一次被调用（递归Calc（n-1）），参数为n-1，当n-1大于1时，Calc（n-1）返回“（n-1）Calc（n-2）”，Calc（n）此时返回值是n（n-1）Calc（n-2），如此反复，一直到Calc函数的参数为1，返回值为1，Calc（n）返回n（n-1）……32*1，函数递归的调用过程如图6.3所示。

    每次调用Calc（）函数，都会为其中的变量（包括形参）开辟栈内存空间，关于函数递归有以下3点需要注意。

    （1）一定要有递归调用终止的条件，且每次调用都向调用终止靠近一步，这能保证递归调用正常结束，不至于出现无限循环，导致系统内存耗尽而崩溃。通常用参数对调用过程进行判断，以便在合适的时候切断调用链，如代码6.12中的“if（n==1）{……}”结构。

    （2）每次调用函数时，都有一定的时空开销，因此，递归函数的效率总比功能相同的循环结构略低，任何用递归编写的函数都可用循环代替，以提高效率。但是，递归带来的好处也是显而易见的：一是程序的可读性比较好，易于修改和维护，二是在函数不断的调用中，函数的规模在减小，在求解阶乘的Calc（）函数例子中，不断用复杂度为n-1的问题来描述复杂度为n的问题，直到问题可以直接求解为止（参数为1）。

    （3）递归函数不能定义为inline函数。

    递归是一种通用的程序设计技术，当一个问题蕴涵递归形式，且关系比较复杂时，采用递归算法往往会自然、简洁，更容易理解（虽然从某种程序上来说会降低效率）。