Hello，我们又见面了，继上次的函数我们讲了库函数，自定义函数，还有实参和形参等等，那我们今天来讲一讲函数递归，函数递归的特点就是以小换大，下面开始我们的讲解
函数递归
- 什么是递归
程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，
递归策略
只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小
- 递归的两个必要特点
存在限制条件，当满足这个限制条件的时候，递归便不再继续。
每次递归调用之后越来越接近这个限制条件。
递归很容易变成死递归，下面是最简单的递归
#include<stdio.h> int main() { printf("haha\n"); main(); return 0; }
一直打印哈哈，一直到栈溢出程序才结束
练习题：接受一个整型值（无符号），按照顺序打印它的每一位。
例如：
输入：1234，输出 1 2 3 4
#include<stdio.h> void print(int n) { if (n>9) { print(n / 10); } printf("%d ", n%10); } int main() { unsigned num = 0;//定义无符号整型，相当于正整数 scanf("%d", &num); print(num); return 0; }
我们输入1234看运行结果
下面我们用画图的方法解释一下
顺序是1-2-3-4-5-6-7
下面我们来讲解一下
1进入print函数中，进行判断，n=1234 ，条件满足，执行print(n/10)
2再次进入print函数，进行判断，n=123，条件满足，执行print(n/10)
3再次进入print函数，进行判断，n=12，条件满足，执行print(n/10)
4再次进入print函数，进行判断，n=1，条件不满足，执行printf(“%d”,n%10)
5代码没有在遇到函数，现在要开始返回到上一个print函数，执行printf(“%d”,n%10)
6继续返回
7最后返回到主函数中的print函数，最后代码停止运行
在上面的整个代码中，我们遇到新的print函数就得进入，一直执行到没有print函数才开始返回，因此可以看出，如果条件n一直大于9的时候就永远进行，这样最后的结果就是栈溢出
我们在写递归的时候必须得要有限制条件，这样才可以递归和回归，才能结束递归
练习题编写函数不允许创建临时变量，求字符串的长度。
#include<stdio.h> #include<string.h> int main() { char arr[] = "abcdef"; int len = strlen(arr); printf("%d", len); return 0; }
我们先写一个普通函数的代码，先不用递归，且我们创建临时变量
#include<stdio.h> int my_strlen(char* arr) { int count = 0; while (*arr != '\0') { arr++; count++; } return count; } int main() { char arr[] = "abcdef"; int len = my_strlen(arr); printf("%d", len); return 0; }
count是来计数的，没执一次地址往后移动一位，在进行判断，满足条件的时候count+1
我们代码要实现上面的这样的效果，也可以写一个用递归的方法
#include<stdio.h> int my_strlen(char* arr)//用指针接收地址 { if (*arr != '\0') { return 1 + my_strlen(arr + 1); } } int main() { char arr[] = "abcdef"; int len = my_strlen(arr); printf("%d", len); return 0; }
我们可以上面的程序运行结果和strlen求出的一样，说明我们的代码正确，那让我现在来分析一下
图比较麻烦，但是实际上过程还是很简单的，如果你仔细看肯定会觉得小编画的怎么和狗屎一样
哈哈哈，开个玩笑，现在我们来分析一下
1从主函数进入函数，进行判断该地址的内容是不是‘\0’，如果不是，继续往下走，又遇到my_strlen(arr + 1);，再次进入函数
2进入函数，进行判断该地址的内容是不是‘\0’，如果不是，继续往下走，又遇到my_strlen(arr + 1); 再次进入函数
3进入函数，进行判断该地址的内容是不是‘\0’，如果不是，继续往下走，又遇到my_strlen(arr + 1); 再次进入函数
4进入函数，进行判断该地址的内容是不是‘\0’，如果不是，继续往下走，又遇到my_strlen(arr + 1); 再次进入函数
5进入函数，进行判断该地址的内容是不是‘\0’，如果不是，继续往下走，又遇到my_strlen(arr + 1); 再次进入函数
6进入函数，进行判断该地址的内容是不是‘\0’，如果不是，继续往下走，又遇到my_strlen(arr + 1); 再次进入函数
7遇到’\0’,条件不满足，开始往返，进入到前面那个函数，往下执行，长度开始加1
8往回进行，长度加1
9往回进行，长度加1
10往回进行，长度加1
11往回进行，长度加1
12往回进行，长度加1
所以最后的长度为6
- 递归和迭代
练习 求n的阶乘
//求n的阶乘 int jie_cheng(int a) { if (a >= 1) { return jie_cheng(a - 1) * a; } } #include<stdio.h> int main() { int n=0; scanf("%d", &n); int x=jie_cheng(n); printf("%d", x); }
当我们看到这里的时候，有没有小伙伴发现我们其实在函数写递归的时候，发现他好像和我们的数学公式有点相似，答案是的，所以当我们想实现一个功能的函数的时候，可以先把他的函数表达式先写出来，然后在写代码
下面呢我们在学习一个斐波那契数列
先介绍一下什么是斐波那契数列，就是前一项加后一项等于后面一项，是从第三个开始的
1 1 2 3 5 8 13 21 34 55
所以我们的公式可以写成F（n）=F（n-1）+F（n-2）当n>3的时候，当n=1 n=2 F(1)=F(2)=1
代码演示
#include <stdio.h> int fib(int n) { if (n <= 2) { return 1; } else return fib(n - 1) + fib(n - 2); } int main() { int n = 0; scanf("%d", &n); int ret = fib(n); printf("第%d个斐波那契数列是：%d", n, ret); return 0; }
虽然上面的代码可以实现我们的效果，但是仍然存在缺陷，如果我们求50的斐波那契数的时候，编译器要计算很长的时间。我们也可以在代码中加入count进行计数，看看重复计算的次数
#include <stdio.h> int count = 0; int fib(int n) { if (n == 3) { count++; } if (n <= 2) { return 1; } else return fib(n - 1) + fib(n - 2); } int main() { int n = 0; scanf("%d", &n); int ret = fib(n); printf("第%d个斐波那契数列是：%d", n, ret); return 0; }
我们可以看到要重复102334155次
很明显这样的代码并不是特别的好，这个时候我们可以用迭代的方法来计算
#include<stdio.h> int fib(int n) { int i = 0; int a = 1; int b = 1; int c = 1; while (n > 2) { c = a + b; a = b; b = c; n--; } return c; if (n == 1 || n == 2) { return 1; } } int main() { int n = 0; scanf("%d", &n); int ret = fib(n); printf("第%d个斐波那契数列是：%d", n, ret); return 0; }
提示
- 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
- 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
- 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销
函数这一课我们也算是完结了，后面会继续分享，大家也一定要每天敲代码，我们下期再见，谢谢大家！
