5.4.2　递归的使用方法

以阶乘计算为例，可以把阶乘计算写成一个单独的函数。

【例5.14】阶乘的计算。

程序运行结果如图5-15所示。

图5-15　运行结果

fact（）函数在其定义内部调用了自身，形成递归。无限制的递归将耗尽计算资源，因此需要设计基例使递归逐层返回。fact（）函数通过if语句给出了n=1时的基例，当n=1时不再递归，返回数值1；如果n为其他正整数，则返回n*（n-1）！。

递归遵循函数的语义，每次调用都会引起新函数的开始，表示它有本地变量值的副本，包括函数的参数。5的阶乘递归过程如图5-16所示。

图5-16　递归函数流程控制图

其实递归是有规律可循的，并且可以看到它甚至还有一定的格式。

①为防止无休止地调用下去，可以加条件判断，满足某种条件后，便不再做递归调用，然后逐层返回。

②函数的递归调用可以分为两个阶段：一是递推阶段，将原问题不断地分解为新的子问题，最终达到已知的条件，这时递推阶段结束；二是回归阶段，从已知条件出发，按照递推的逆过程，逐一求值回归，最终到达递推的开始处，完成递归调用。

【例5.15】把M个同样的苹果分放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？例如，M=7，N=3，则有（7，0，0）、（6，1，0）、（5，2，0）、（5，1，1）、（4，3，0）（4，2，1）、（3，3，1）和（3，2，2）共8种分法。注意，（5，1，1）和（1，5，1）是同一种分法。

解题分析：

设f（m，n）为m个苹果、n个盘子的分法数目，则先对n做讨论：

①当n>m时，则必定有n-m个盘子永远空着，去掉它们，对摆放苹果方法数目不产生影响。即f（m，n）=f（m，m）。

②当n≤m时，分法可以分成两类：含有0的方案数和不含有0的方案数。

含有0的方案数，即有至少一个盘子空着，即相当于f（m，n）=f（m，n-1）；不含有0的方案数，即所有的盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同方法的数目，即f（m，n）=f（m-n，n）。总的放苹果的方法数目等于两者的和，即f（m，n）=f（m，n-1）+f（m-n，n）。

递归出口条件说明：

当n=1时，所有苹果都必须放在一个盘子里，所以返回1；

当m=0（没有苹果可放）时，定义为1种方法。

程序如下：

程序运行结果如图5-17所示。

图5-17　运行结果