递归算法

递归算法，通常有以下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); }