关于递归算法的几个例子(C语言)
2018-06-18 04:00:16来源:未知 阅读 ()
1.递归算法的定义:
2.递归与迭代的优劣
eg1:斐波那契数列:斐波那契数列(Fibonacci sequence),又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=1,F(1)=1, F(n)=F(n-1)+F(n-2)(n>=2,n∈N*)
1 /* 2 斐波那契数列 迭代实现 (打印出前40个) 3 */ 4 #include <stdio.h> 5 int main(){ 6 int i, arr[40]; 7 arr[0] = 0; 8 arr[1] = 1; 9 printf("%d %d ",arr[0],arr[1]); 10 for(i=2; i<40; i++){ 11 arr[i] = arr[i-1] + arr[i-2]; 12 printf("%d ",arr[i]); 13 } 14 printf("\n"); 15 16 return 0; 17 18 }
1 /* 2 斐波那契数列 递归实现 (打印出前40个) 3 */ 4 #include <stdio.h> 5 /* 6 int fb(int n){ 7 if(n == 0){ 8 return 0; 9 }else if(n == 1){ 10 return 1; 11 }else{ 12 return fb(n-1) + fb(n-2); 13 } 14 } 15 */ 16 17 int fb(int n){ 18 if(n<2){ 19 return n == 0? 0:1; 20 }else{ 21 return fb(n-1) + fb (n-2); 22 } 23 24 } 25 26 27 int main(){ 28 int i; 29 for(i=0; i<40; i++){ 30 printf("%d ",fb(i)); 31 } 32 printf("\n"); 33 34 return 0; 35 }
eg2:阶乘:亦即n!=1×2×3×...×n。阶乘亦可以递归方式定义:0!=1,n!=(n-1)!×n。
1 /* 2 递归实现阶乘 3 递归方式定义:0!=1,n!=(n-1)!×n。 4 */ 5 6 #include <stdio.h> 7 int fact(n){ 8 if(n == 0){ 9 return 1; 10 }else{ 11 return fact(n-1) * n; 12 } 13 } 14 15 int main(){ 16 int n = 5; 17 printf("%d\n",fact(n)); 18 return 0; 19 }
eg3:
1 #include <stdio.h> 2 int print(){ 3 char a; 4 scanf("%c", &a); 5 if(a != '#'){ 6 print(); 7 } 8 if(a != '#'){ 9 printf("%c",a); 10 } 11 return 0; 12 } 13 int main(){ 14 print(); 15 printf("\n"); 16 return 0; 17 }
解题思路:
eg4:二分法查找
1 /* 2 二分法查找:迭代实现 3 */ 4 #include <stdio.h> 5 int main(){ 6 int arr[10] = {1,2,3,4,5,6,7,8,9,10}; 7 int input, low, high, mid; 8 low = 0; 9 high = 9; 10 mid = (low + high) / 2; 11 scanf("%d", &input); 12 13 while(input != arr[mid]){ 14 if(input < arr[mid]){ 15 high = mid; 16 mid = (low + high) / 2; 17 }else{ 18 low = mid; 19 mid = (low + high) / 2; 20 } 21 } 22 printf("%d ",mid);/*输出要查找数字在数组中的下标*/ 23 return 0; 24 25 }
1 /* 2 二分法查找:递归实现 3 */ 4 5 #include <stdio.h> 6 int fun(int low, int high, int input, int arr[]){ 7 int mid; 8 mid = (low + high) /2; 9 if(arr[mid] == input){ 10 return mid; 11 }else{ 12 if(input < arr[mid]){ 13 high = mid; 14 return fun( low, high, input, arr); 15 }else{ 16 low = mid; 17 return fun( low, high, input, arr); 18 } 19 } 20 21 } 22 int main(){ 23 int arr[10] = {1,2,3,4,5,6,7,8,9,10}; 24 int input, low, high; 25 low = 0; 26 high = 9; 27 scanf("%d", &input); 28 printf("%d \n",fun(low, high, input, arr));/*输出要查找数字在数组中的下标*/ 29 return 0; 30 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:(3)C语言——狐狸和兔子的故事
- C++ rand函数 2020-06-10
- 关于各种不同开发语言之间数据加密方法(DES,RSA等)的互通的 2020-06-07
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash