题源：中科院软件所 1997 二，1（9分）

设m,n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。

例：f(5,3)=5，有五种表示方式：

3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1

请补全递归代码。

答案

#include<stdio.h>

int f(int m, int n);
int main()
{
    int m,n,ans;
    scanf("%d%d",&m,&n);
    ans = f(m,n);
    printf("%d\n",ans);
}
 
int f(int m, int n)
{
    if(m == 1)
    	return 1;
    if(n == 1)
    	return 1;
    if(m == n)
    	return (1 + f(m, n-1));
    else if(m < n)
    	return f(m, m)
    else	// (m > n)
    	return (f(m - n, n) + f(m, n - 1));
}

第一行定义了f(m,n)这个函数,返回值即表示方式的数目,为一个整数.

第二行定义了 m 和 n 这两个自变量为整数.

if (m==1) return 1;这里是说如果m等于1,则函数的返回值为1,显然1只能分解为1,也即表示方式只有一种.

if (n==1) return 1;这里是说如果n等于1,则函数的返回值为1,显然无论m多大,n为1时只能表示为m个1之和,也即表示方式只有一种.

当m>n时，f(m,n) 可以递归地分解为两种情况：
当最大加数包含n时，即f(m-n, n)
当最大加数不包含n时，即f(m, n-1)

以 f(6, 4) 为例：

而当 m>n 时，比如 f(6,4)，可以分成两类讨论：

• 如果最大的加数为3，则按照定义共有f(6,3)种表示方法；
• 而剩下的表示方法中必然有一个最大的加数4，由于总和为6，因此可知其余的加数之和为6-4=2，而要使小于等于4的自然数之和等于2，按照函数定义，共有f(2,4)种可能性。
• 因此，f(6,4) = f(6,3) + f(2,4)。