3.1　计算递归函数

数学上常用的阶乘函数、幂函数、斐波那契数列，其定义和计算都是递归的。例如，对于自然数n，阶乘n!的递归定义为。按阶乘n!的递归定义，求解n!的递归函数fac(n)如下。

---

int  fac(int n)；
{
    if (n==0) return 1；            //判断递归边界
    if (n>=1) return n*fac(n-1)；   //处理递归并返回结果
}

---

显然，递归程序的最大优点是程序简明、结构紧凑。这种直接从问题定义出发编程的方法最便于人们阅读和理解。但问题是，递归过程中的状态变化比较难掌握，效率也比较低。以fac(3)为例，它的执行流程如图3.1-1所示。

图　3.1-1

程序中fac(0)=1称为递归边界。fac(3)→fac(2)→fac(1)→fac(0)称为递归过程，接下来的fac(0)→fac(1)→fac(2)→fac(3)是一个回代过程（fac(0)=1回代给fac(1)，fac(1)的值回代给fac(2)……直至求出fac(3)=6）。

类似地，对于自然数n，计算斐波那契数列的函数fib(n)递归定义为，根据递归定义的形式，可写出如下递归函数：

---

int fib(int n);
{ if (n<=1) return  n；                    //递归边界
    if (n>1) return  fib(n-1)+fib(n-2)；   //递归步骤
}

---

从上述两个例子可以得到如下启示。

1）用递归过程求解递归定义的函数，递归过程可直接按照递归函数的定义结构编写。

2）对于一个较复杂的问题，若能够分解成几个相对简单且解法相同或类似的子问题，只要解决了这些子问题，则原问题就迎刃而解，这就是递归求解。例如，计算阶乘4!时先计算3!，将3!的结果值回代就可以求出4!（4!=4*3!）了。这种分解–求解的策略叫“分治法”。

3）当分解后的子问题可以直接解决时，就停止分解，可直接求解的子问题称为递归边界。递归的过程就是不断地向递归边界靠近，若递归函数无法到达边界，则程序会因栈溢出而失败退出。例如，阶乘的递归边界是fac(0)=1，斐波那契数列的递归边界是fib(0)=0，fib(1)=1。

【3.1.1　放苹果】

把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？用k表示不同的分法。5、1、1和1、5、1是同一种分法。

输入

第一行是测试用例的数目t（0≤t≤20）。以下每行均包含两个整数m和n，以空格分开，1≤m,n≤10。

输出

对输入的每个测试用例m和n，用一行输出相应的k。

试题来源：lwx@POJ

在线测试：POJ 1664

试题解析

设f(m,n)是m个同样的苹果放在n个同样的盘子里的方法数，对f(m,n)的分析和递归定义如下。

1）n>m：至少有n-m个盘子会空着，去掉这n-m个盘子对放苹果的方法数不会产生影响，即f(m,n)=f(m,m)。

2）n≤m：不同的放法可以分成两类。

·至少有一个盘子没有放苹果，即f(m,n)=f(m,n-1)。

·所有盘子里都有苹果，如果从每个盘子里拿走一个苹果，不会影响方法数，即f(m,n)=f(m-n,n)。

所以，当n≤m时，根据加法原理，放苹果的方法数等于上述两者的和，即f(m,n)=f(m,n-1)+f(m-n,n)。

对f(m,n)的递归边界分析如下：

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

2）当m==0时，没有苹果可放，定义为1种放法，f(m,n)返回1。

递归过程，或者是n减少，向递归边界逼近，最终到达递归边界n==1；或者是m减少，当n>m时，f(m,n)返回f(m,m)，最终到达递归边界m==0。

参考程序

---

#include<cstdio>
using namespace std;
int f(int m,int n)             //递归函数：计算m个同样的苹果放在n个同样的盘子里的方法数
{
    if(n==1||m==0)             //处理递归边界
        return 1;
    if(m<n)                    //处理情况n>m
        return f(m,m);
    else                       //处理情况n≤m
        return f(m,n-1)+f(m-n,n);
}
int main()
{
    int t;
    scanf("%d",&t);            //输入测试用例数
    while(t--)                 //依次处理每个测试用例
    {
        int m,n;
        scanf("%d%d",&m,&n);   //输入苹果数和盘子数
        printf("%d\n",f(m,n)); //计算和输出m个苹果放在n个盘子里的方法数
    }
    return 0;
}

---