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 }
没有人陪你走一辈子，所以你要适应孤独，
