放苹果 （递归）

例题: 放苹果
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法? 5，1，1和1，5,1是同一种分法。
输入
第一行是测试数据的数目t( 0 <= t<= 20)。以下每行均包含二个整数M和N，以空格分开。1<=M,N<=10。
输出
对输入的每组数据M和N，用一行输出相应的K。
样例输入
1
7 3
样例输出
8

 用递归将问题分解为规模更小的子问题进行求解
设i个苹果放在k个盘子里放法总数是f (i，k)，则:
i<k时，多余的盘子忽略，相当于i个苹果放到i个盘子里
  f(i,k) = f(i,i)
i>=k 时，总放法= 有盘子为空的放法(即盘子减少1个)+没盘子为空的放法(先每个盘子都放一个，再将剩余的i-k放到k个盘子中)
  f(i,k) = f(i,k-1) + f(i-k,k)
边界条件? 

当苹果放完时（i=0）,算一种方案 return 1

当盘子放完了，苹果还剩时，该方案不成立 return 0

#include <iostream>

using namespace std;

int f(int m,int n)
{
    if(m<n)
        return f(m,m);
    if(m==0)
        return 1;
    if(n==0)
        return 0;
    return f(m,n-1)+f(m-n,n);
}

int main()
{
    int m,n,cnt;
    cin>>cnt;
    while(cnt--)
    {
        cin>>m>>n;
        cout<<f(m,n)<<endl;
    }

    return 0;
}