三. 函数递归典型例题的实现
这里在写几道题巩固理解💪
3.1 🥰求n的阶乘
3.1.1题目描述
用递归的方法求n的阶乘（不考虑溢出问题） 例如： 输入：4，输出 24
3.1.2解题思想
n的阶乘为1234…(n-1)n，我们可以先用递推的思想，先算出n(n-1)的值，再用n(n-1)的值乘以(n-2),这样依次乘下去，以n=1为限制条件，返回1。然后再用回归思想，返回回去，及可得到n的阶乘。
3.1.3代码实现
#include<stdio.h> int factorial(int n) { if (n == 1) return 1; else return n * factorial(n - 1); } int main() { int n = 0; scanf("%d", &n); int ret = factorial(n); printf("n的阶乘为：%d", ret); return 0; }
3.1.4执行结果
3.1.4递归流程图
3.2👉strlen函数的模拟实现
3.2.1题目描述:
用递归的方法模拟实现strlen函数 例如： 输入：abc，输出 3
3.2.2 解题思想
strlen函数遇到 ’\0’才会停止，所以我们以 ’\0’为限制条件，我们每调用一次我们自己实现的my_strlen函数，次数就加一，直到遇到 ’\0’停止。
3.2.3 代码实现
int my_strlen(char* str) { if (*str != '\0') { return 1 + my_strlen(str + 1); //str是数组的首地址 } return 0; } int main() { char a[] = "abcdefg"; int ret = my_strlen(a); printf("%d", ret); return 0; }
3.2.4执行结果
3.3🍒求n的k次幂
3.3.1题目描述
用递归的方法实现n的k次幂 例如： 输入：3,3，输出 27
3.3.2解题思路
解题思路：以k>0和k=0为限制条件，每一次递推就乘以n，并且k都减一次1，直到不满足限定条件，然后回归，即为27。
3.3.3代码
#include<stdio.h> int power(int n, int k) { if (k > 1) { return power(n, k - 1) * n; } else return n; } int main() { int n = 0; int k = 0; scanf("%d", &n); scanf("%d", &k); int ret = power(n, k); printf("%d ", ret); return 0; }
3.3.4执行结果
3.5🍒斐波那契数📌
3.5.1 题目描述
计算斐波那契数递归实现求第n个斐波那契数 例如：输入：5 输出：5 输入：10， 输出：55
3.5.1 解题思路
斐波那系数是前两项加起来等于后一项：1，1，2，3，5，8，13…,所以我们可以以n<=2为限制条件，当n=1或2时，返回1，然后到n=3项时就是n=1项和n=2项之和，然后依次往后推，即Fib(n)就是Fib(n-1)和Fib(n-2)之和。
3.5.2.1非递归求解
#include<stdio.h> int fac(int n) { int a=1, b=1, res=0; if (n == 1 || n == 2) { return 1; } else { for (int i = 3; i <= n; i++) { res = a + b; a = b; b = res; } } return res; } int main() { int n; scanf("%d", &n); printf("%d",fac(n)); return 0; }
3.5.2.2执行结果
3.5.3.1递归求解
#include<stdio.h> int fac(int n) {//斐波那契非递归 int a=1, b=1, res=0; if (n == 1 || n == 2) { return 1; } else { return fac(n - 1) + fac(n - 2); } } int main() { int n; scanf("%d", &n); printf("%d",fac(n)); return 0; }
3.5.3.2执行结果
🍭斐波那契数的非递归的实现优于递归实现的原因
1.因为每一次函数递归（函数调用）都会在函数栈帧上开辟一块空间，所谓的压栈。这样会大大降低我们代码的执行效率。
2用递归法实现的斐波那契数正对应了其缺点，因为它的递推时会有很多分支，一个分支下面又有很多分支，每一个小分支都是函数的调用，然而还有回归，函数栈帧需要销毁，这会大大降低代码的执行效率，如果n=50，则代码执行时间都要1个多小时，所以用递归法实现的斐波那系数其实是不实用的。
3.而用非递归的方法实现，可以大大提高代码的运行效率。只是每一次循环，n1,n2,tmp会被赋值，代码执行次数大大减少，所以斐波那契数的非递归的实现优于递归实现的。
