递归算法：基本含义，一个函数或者数学结构，如果在其定义或说明内部直接或间接得出现对其本身的引用，或者是为了描述问题的某一个状态，必须要用它的上一个状态，而描述上一个状态，又必须用到它的上一个状态，这种定义，称为递归或递归定义。在程序设计上，当函数直接调用本身或者间接调用本身，称为递归调用。
递归的最简单应用：通过各项关系及初值求数列的某一项。（1）
比如阶乘数列
1、2、6、24、120、720……
如果用上面的方式来描述它，应该是：
，程序实现
int fun(int x)
{
if(x == 1)
return 1;
return n*fun(n-1);
}
(2)找出组合数
找出从自然数1、2、……、n中任取r个数的所有组合。例如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
（7）4、3、2 （8）4、3、1 （9）4、2、1
（10）3、2、1
如何实现呢？
首先分析10个组合，我们可以采用递归来实现，假设函数为combo(int m,int n);为找到自然数1-m中任取K个数组合，当第一个数选定后，后面的k-1个数是从m-1各数中选择得到。我们发现这将是将m选k个数转换为m-1个数中选k-1个数的组合数。为了解决此问题，我们可以定义个数组A，数组的第一个元素为k，约定函数将确定的k个数字的组合第一个数放在A[k]中，当一个组合求出后，才将数组A的一个组合输出，第一个数可以是m-k，函数将确定组合的第一个数放入数组后，有两种可能的选择，因还未到顶组合的其余元素，继续递归确定，或因一确定了组合的全部元素，输出这个组合，
具体代码：
//递归求解组合数
#define MAX 100
int a[MAX];
void combo(int m,int k)
{
int i,j;
for (i = m;i>=k;i--)
{
a[k] = i;
if (k>1)
{
comb(m-1,k-1);
}
else
{
for (j = a[0];j>0;j--)
{
printf("%4d",a[j]);
}
printf("\n");
}
}
}
更多的练习，
前几天在博客园看到有人面试时，遇到递归算法题，一时手痒就解了一个。顺便网上又找来几个，也实现了。给大家分享一下，开阔一下思路，没准你明天面试就能用上。
1、编写一个方法用于验证指定的字符串是否为反转字符，返回true和false。请用递归算法实现。（反转字符串样式为"abcdedcba"）
2、一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第30个是多少
3、一列数的规则如下: 1、12、123、1234、12345、123456......,求第n个数的递归算法（n<=9）。
4、将一整数逆序，如987654321变为123456789。
5、一个射击运动员打靶,靶一共有10环,连开10枪打中90环的可能行有多少种?
posted on 2011-10-22 21:22
mengkai 阅读(615)
评论(0) 编辑 收藏 引用 所属分类:
algorithm