关于递归算法的几个例子(C语言)

2018-06-18 04:00:16来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:(2)c语言求两个日期相隔的天数(闰年)

下一篇:(3)C语言——狐狸和兔子的故事