递归算法设计,通常有以下3个步骤:
1.
问题,得出递归关系。
2. 设置边界条件,控制递归。
3. 设计函数,确定参数。
我们来看一个简单的应用。
例3:楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法。例如,当n=3时,共有3种走法,即1+1+1,1+2,2+1。
算法分析:设n阶台阶的走法数为f(n),显然有:
1 n = 1
f(n) = { 2 n = 2
f(n-1) + f(n-2) n > 2
得到相应的函数如下:
int F(int n)
{
if (n == 1 || n == 2)
return n;
return F(n-1) + F(n-2);
}
例4:整数划分的问题:对于一个整数n的划分,就是把n表示成一系列的正整数的和的表达式,注意划分与次序无关.
例如,6可以可以划分为:
6;
5+1;
4+2,4+1+1;
3+3,3+2+1,3+1+1+1;
2+2+2,2+2+1+1,2+1+1+1+1;
1+1+1+1+1+1
现在问题是,给一个n求他的所有划分.
这个问题初看,很难找出大规模问题与小规模问题之间的关系,我们注意了,对于上面的第一行,所有加数不超过6,第2行, 所有加数不超过5,.....第6行所有加数不超过1.因此,我们可以定义一个q(n, m)的函数,表示 n所有加数不超过m的划分数目.所以n的划分总数目可以表示为q(n, n).那我们怎样才能把找出q(n, n)的递归关系呢?
很显然,我们可以立即得到以下关系,
q(n,n) = q(n,n-1) + 1;
所以问题规模变小,但是我们很不能根据这个关系转化为更小的问题,所以我们主要考虑这种情况:q(n, m)(其中m < n),怎样把这中情况分解呢。我们尝试的把q(n, m)变为q(n, m-1);我们惊奇的发现,只要把q(n, m-1)加上包含加数m的项就等于q(n, n),即q(n, m) = q(n, m-1) + 包含m加数的表达式数。例如m = 4,我们可以把q(n, 4) = q(n, 3) + 2(包含4加数的表达使有两个:4+2, 4+1+1)。而我们发现,包含4的表达可以转化为q(n-4, 4) (想想?),所以的递归关系式就出来了:
q(n,m) = q(n,m-1) + q(n-m,m);
接下来就是找边界条件了,我们知道当n = 1时,q(n, n) = 1;当m =1时,q(n, m)
= 1;有了边界条件,我们递归基本上完成了.得到递归公式:
1, n = 1, m = 1;
q(n,m) = { q(n,n), n < m;
1 + q(n, n-1), n = m;
q(n,m-1) + q(n-m,m), n > m > 1.
编写代码如下:
#include
int F(int n,int m);
int main()
{
int i;
for (i=1; i<21; i++)
printf("%d - %d\n", i, F(i, i));
getchar();
return 0;
}
int F(int n, int m)
{
if (n == 1 || m == 1)//递归出口
return 1;
if (n == m)
return F(n, n-1) + 1;
else if (n < m)
return F(n, n);
else
return F(n, m-1) + F(n-m, m);
}