所谓递归，简而言之就是应用程序自身调用自身，以实现层次数据结构的查询和访问。 递归的使用可以使代码更简洁清晰，可读性更好（对于初学者到不见得），但由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多，而且，如果递归深度太大，可能系统资源会不够用。
递归分为直接递归和间接递归：简而言之，在函数中直接调用函数本身，称为直接递归调用。在函数中调用其它函数，其它函数又调用原函数，这就构成了函数自身的间接调用称为间接递归调用。
利用递归算法解题，首先要对问题的以下三个方面进行分析： 一、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。
简单地说，函数下一次的参数是函数自身上一次的输出值，也就是说，函数的下一次执行取决于上一次的结果，即自身依赖。如求阶乘算法：
1 #include <stdio.h>
2
3 float fun(float n)
4 {
5 if (n<0)
6 {
7 exit(-1);
8 }
9 else if (n==0||n==1) //退出条件
10 {
11 return 1;
12 }
13 else
14 return n*fun(n-1); //递归调用
15
16 }
17
18
19 void main(void)
20 {
21 int n;
22 printf("请输入数(n!):\n");
23 scanf("%d",&n);
24 printf("%.f",fun(n)); //不显示小数部分的输出
25 return;
26 }
我们从递归函数fun中，可以得到：1）必须有退出条件(if)；2）每次调用参数不同，但有一定的规律民（n-1)；3)自身的输出作为自身的输入return。
1 #include <stdio.h>
2 #include <string.h>
3 void fun(char *s, int n, int b)
4 {
5 char bit[]={"0123456789ABCDEF"};
6 int len;
7 if(n==0)
8 {
9 strcpy(s,"");
10 return;
11 }
12 fun(s, n/b, b);
13 len = strlen(s);
14 s[len] = bit[n%b];
15 s[len+1] = '\0';
16 }
17
18 void main(void)
19 {
20 char s[80];
21 int i, base,old;
22 printf("请输入十进制数:");
23 scanf("%d",&old);
24 printf("请输入转换的进制：");
25 scanf("%d", &base);
26 fun(s, old, base);
27 printf("%s\n", s);
28
29 return;
30 }
我们从递归函数fun中，可以得到：1）必须有退出条件，函数；2）每次调用参数不同，但有一定的规律民（n/b)；3)逆向结果处理。
经典例子：
1 求全排列
1 #include<stdio.h>
2 #define SWAP(a,b,t) ((t)=(a),(a)=(b),(b)=(t))
3
4 //求全排列，list存放着要排列的的数据，i控制着排列的结束，
5 //如果第一次调用，一般为0，n是list中数据的大小，或长度。
6 void perm(char *list,int i,int n)
7 {
8 int j;
9 int temp;
10 if(i == n) //一个全排列已经完成，打印整个排列
11 {
12 for(j = 0; j <=n; j++)
13 {
14 printf("%c",list[j]);
15 }
16 printf("\n");
17 }
18 else
19 {
20 for(j = i; j <= n; j++)
21 {
22 SWAP(list[i],list[j],temp); //依次将1，2，...n个元素放在第一个位置
23 perm(list,i+1,n); //递归进行全排列
24 SWAP(list[i],list[j],temp); //由于第一个SWAP将第j个元素放到第一个位置进行了
25 //递归全排列，这里就将列表还原，以进行第2次递归
26 }
27 }
28 }
29
30 int main()
31 {
32 char list[3] = {'a','b','c'};
33 perm(list,0,2);
34 return 0;
35 }
2斐波那契数列
又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……这个数列从第三项开始，每一项都等于前两项之和。又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？
1 #include<stdio.h>
2 int fun(int n)
3 {
4 if(n==0||n==1)
5 {
6 return 1;
7 }
8 else
9 return fun(n-1)+fun(n-2);
10 }
11
12 int main()
13 {
14 int n;
15 printf("please input month number\n");
16 scanf("%d",&n);
17 printf("%d\n",fun(n));
18
19 return 0;
20 }
3 汉诺塔
4求一组整数中的最大(小)值（整数是一个int[]数组，个数未知）。
参考资料