c 递归函数浅析 递归算法及经典递归例子代码实现
所谓递归,简而言之就是应用程序自身调用自身,以实现层次数据结构的查询和访问。 递归的使用可以使代码更简洁清晰,可读性更好(对于初学者到不见得),但由于递归需要系统堆栈,所以空间消耗要比非递归代码要大很多,而且,如果递归深度太大,可能系统资源会不够用。
递归分为直接递归和间接递归:简而言之,在函数中直接调用函数本身,称为直接递归调用。在函数中调用其它函数,其它函数又调用原函数,这就构成了函数自身的间接调用称为间接递归调用。
利用递归算法解题,首先要对问题的以下三个方面进行分析: 一、决定问题规模的参数。需要用递归算法解决的问题,其规模通常都是比较大的,在问题中决定规模大小(或问题复杂程度)的量有哪些?把它们找出来。二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解?这就是问题的边界条件及边界值。三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题,需要通过哪些步骤或等式来实现?这是解决递归问题的难点。
简单地说,函数下一次的参数是函数自身上一次的输出值,也就是说,函数的下一次执行取决于上一次的结果,即自身依赖。如求阶乘算法:
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[]数组,个数未知)。
参考资料