计算机等级:常用算法设计方法

递归算法的执行过程分为递归和回归两个阶段。在递归阶段，一个更复杂的问题(规模n)的解被推到一个比原问题更简单的问题(规模小于n)的解。例如，在上面的例子中，求解fib(n)被推至求解fib(n-1)和fib(n-2)。也就是说，为了计算fib(n)，首先要计算fib(n-1)和fib(n-2)，然后再计算fib(n-3)和fib(n-4)。依此类推，直到fib(1)和fib(0)被计算出来，结果1和0可以分别立即得到。在递归阶段，递归必须终止。例如，在函数fib中，当n为1和0时。
在回归阶段，得到最简单情况的解时，循序渐进，依次得到稍微复杂问题的解。例如，在获得fib(1)和fib(0)后，返回fib(2)的结果，在编写递归函数时，需要注意的是，对函数中局部变量和参数的了解仅限于当前调用层。当它被推到“简单问题”层时，原始层中的参数和局部变量将被隐藏。在一系列“简单问题”层中，它们都有自己的参数和局部变量。
由于递归引起一系列的函数调用，并且可能有一系列的重复计算，所以递归算法的执行效率比较低。当递归算法可以很容易地转换成递归算法时，程序通常是根据递归算法编写的。比如上面例子中用来计算斐波那契数列第n项的函数fib(n)就应该采用递归算法，即从斐波那契数列的前两项开始，依次从前两项开始计算下一项，直到计算出所需的第n项。
[问题]组合问题
问题描述:从自然数1，2，...，n .比如n=5，r=3的所有组合是:(1)5，4，3 (2)5，4，2 (3)5，4，1
(4)5，3，2 (5)5，3，1 (6)5，2，1。设void comb(int m，int k)是从自然数1，2，...当组合的第一个数字被选择时，随后的数字是来自剩余m-1个数字的k-1个数字的组合。从而将从m个数中取k个数的组合问题转化为从m-1个数中取k-1个数的组合问题。假设在工作数组a[]中引入函数存储得到的组合数，约定函数将确定的K个数组合的第一个数放入a[k]中。当获得一个组合时，将输出[]中的一个组合。第一个数字可以是M，m-1，...在函数将确定的组合的第一个数字放入数组后，有两种可能的选择。因为组合的其余元素还没有去掉，所以继续递归确定；或者因为已经确定了组合的所有元素，所以输出该组合。详见下面程序中的函数梳。
[程序]
#包含
#定义maxn 100
int a[maxn]；
void comb(int m，int k)
{ int i，j；
for(I = m；I > = k；I-)
{ a[k]= I；
如果(k>1)

梳子(i-1，k-1)；
else
{ for(j = a[0]；j > 0；j - )
printf("M "，a[j])；
printf(" ")；
}
}