7.递归实现找到第n个斐波那契数
①.递归实现
递归题目里估计最著名的就是斐波那契数了，但是递归的写法其实并不高效，笔者进行了修改，使得各位可以看到它的弊端
//仅仅表达思想递归: //斐波那契数列 1 1 2 3 5 8 13 21 34 55 int count = 0; int Fib(int n) { if (n == 4) count++;//计算重复度,重复度过大,时间浪费 if (n <= 2) { return 1; } else return Fib(n - 1) + Fib(n - 2);//效率低是因为重复很多 } int main() { //第n个斐波那契数 int n = 0; scanf("%d", &n); int fib = Fib(n); printf("%d\n", fib); printf("%d\n", count); return 0; }
第三个数就是笔者测试的(笔者输入的是4)重复计算的个数高达接近20万.可见这个递归实现有多么低效。而且仅仅对于第50个数就需要很长时间计算。可以说十分鸡肋。
②非递归
int Fib(int n) { int a = 1; int b = 1; int c = 0; while (n >= 3) { c = a + b; a = b; b = c; n--;//进来几次,算几次 } return c; } int main() { //第n个斐波那契数 int n = 0; scanf("%d", &n); int fib=Fib(n); printf("%d\n", fib); return 0; }
这个非递归实现还是挺有意思的。笔者利用图解可以让大家更加理解。
8.青蛙跳台阶问题
青蛙每次可以选择跳一个或者两个台阶，那么青蛙要跳到第n个台阶需要多少种跳法呢？
我们可以简单分析一下：
那么代码就可以实现：
int fib(int n) { if (n <= 2) return n; else { return fib(n - 1) + fib(n - 2); } } int main() { int n = 0; scanf("%d", &n); printf("%d", fib(n)); return 0; }
9.逆向输出字符串
逆向输出字符串
//常规实现 void reverse_string(char* str) { int count = 0; char* arr = str; while (*str != '\0') { count++; str++; } int left = 0; int right = count - 1; while(left <= right) { char tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp; left++; right--; } }
递归实现：
#include<string.h> void reverse_string(char* str) { int count = strlen(str); char tmp = str[0]; str[0] = str[count - 1]; str[count - 1] = '\0'; if (strlen(str+1) >= 2) { reverse_string(str + 1); } str[count - 1] = tmp; } int main() { char arr[] = "qwertyu"; reverse_string(arr); printf("%s\n", arr); return 0; }
这个递归是如何操作的呢？首先笔者认为要根据这个字符串思考常规实现是如何转化为递归实现。很明显，基本思想是俩俩交换。见图
10.计算排列数
输入两个数，计算A(n上)(m下)😂。
#include<stdio.h> int arrange(int n,int m) { if(m) { return n*arrange(n-1,m-1); } else return 1; } int main() { int n,m; scanf("%d%d",&n,&m); int ret=arrange(n,m); printf("%d\n",ret); return 0; }
11.汉诺塔问题(Hanoi)
题目笔者就不多赘述了。
图解：
代码实现：
//汉诺塔问题 void move(char pos1, char pos2) { printf("%c->%c ", pos1, pos2); } void Hanoi(int n, char pos1, char pos2,char pos3) { if (n == 1) { move(pos1, pos3); } else { Hanoi(n - 1, pos1, pos3, pos2); move(pos1, pos3); Hanoi(n - 1, pos2, pos1, pos3); } } int main() { //笔者为了直观展示结果，多加了几个，其实只需一个就可以了 int n,m,k; scanf("%d", &n); Hanoi(n, 'A','B', 'C'); printf("\n"); scanf("%d", & m); Hanoi(m, 'A', 'B', 'C'); printf("\n"); scanf("%d", &k); Hanoi(k, 'A', 'B', 'C'); return 0; }
对比图一下：
可以发现是可以吻合的。但是注意汉诺塔问题n值不能过大，通过图解诸君已经可以发现它的执行也是比较繁琐的，需要2^n-1次，指数爆炸还是挺恐怖的。
通过上面几个简单的题目就可以发现递归的好处，化繁为简。笔者认为，递归本身是比较抽象的，建议诸君在做这类题目的时候可以通过画图的形式进行剖析，那么就比较好解。要注意递归的限制条件和它的循环是怎么设计去接近这个条件，这一点是比较重要的。
但是递归也是有它的弊端：
递归层数太深会出现栈溢出的。
解决方案
1.递归改为非递归
2.非静态改为静态//不在栈上挪到静态区。
