我所使用的编译器是VS2022

目录

1. 什么是递归
2. 递归的举例
3. 递归与迭代
4. 最终的总结

一、什么是递归

递归的编程思想就是：函数自己调用自己

1.1递归的思想

做到大事化小，繁事变简，将复杂的问题拆解成范围更小的子问题，子问题继续拆分，直到遇到一个临界条件，终止拆分，子问题算出结果后，再一步步回溯，直到全部回溯完成

1.2递归的限制条件

输入递归代码时，需保证两点：

• 递归必须要有限制条件，防止死递归，还会随带着栈溢出的问题存在
• 递归必须每一次执行调用自身函数后，都需要更加接近这个限制条件，让递归可以正常结束

二、递归的举例

2.1n的阶乘

int Fact(int n) { if (n == 0) //递归终止条件 return 1; else return n * Fact(n - 1); }

这个函数就是在Fact（）函数中又调用了Fact（）函数，这就是递归，我们是如何想到这样写递归代码的呢？其实很简单，我们只需要列出公式，递归代码就很好写出来了

可以看到，我们上述写的递归代码和我们的公式非常类似，有公式写递归就非常容易

代码测试：

#include <stdio.h> int Fact(int n) { if (n == 0) return 1; //递归终止条件 else return n * Fact(n - 1); } int main() { int n = 0; scanf("%d", &n); int ret = Fact(n); printf("%d\n", ret); return 0; }

运行截图：

下面我们给出一个图片，来表示上述输入5时此递归函数执行的流程：

我们来分析一下此递归流程，递归分为递推和回溯，和上述图片的流程一样

递推开始

• 首先，当n为5进来时，因为5不是0，所以会执行5*Fact（4）
• 接着，4进去，4不是0，会执行4*Fact（3）
• 接着，3进去，3不是0，会执行3*Fact（2）
• 接着，2进去，2不是0，会执行2*Fact（1）
• 接着，1进去，1不是0，会执行1*Fact（0）
• 0进去，遇到递归终止条件，n==0，此时返回1，也就是Fact（0）==1，开始一层一层回溯

开始回溯

• 先回溯到1*Fact（0），结果为1，也就是Fact（1）为1
• 再回溯到2*Fact（1），结果为2，也就是Fact（2）为2
• 再回溯到3*Fact（2），结果为6，也就是Fact（3）为6
• 再回溯到4*Fact（3），结果为24，也就是Fact（4）为24
• 最后回溯到5*Fact（4），结果为120，然后return返回了最刚开始的5*Fact（4）的值，也就是120

总结：递归就是，分为( 递推＋回溯 )两个部分，从Fact(5)开始根据终止条件往下递推，递推到Fact(0)时，n==0，达到终止条件，开始往回回溯，回到到Fact(5)，也就是：从哪里开始递推，最后就回溯到哪里，从哪开始就从哪结束

2.2按顺序打印整数的每一位

比如输入1234，我们要打印出1 2 3 4的效果，每个数中间加了空格

想要用递归实现这个功能，我们可以拆分一下怎么获得这样的效果

首先，1234，我们可以拆分成123+4，先打印123，再打印4，再拆成12+3+4，先打印12，再打印3和4，再拆除1+2+3+4，先打印1，再接连打印2,3,4。

这其实就是递归的思想，我们把1234，从4拆到1，再从1归回到4，回归的过程也就是我们打印的过程，只需要在每次回归打印时加个空格就能达到想要的效果

我们用（整数%10）获取整数的最后一位，（整数/10）获得整数的前n-1位（n是整数的位数）

代码测试：

void Print(int num) { if (num >9)//终止条件，当num为个位数时，开始回溯 { Print(num / 10); } printf("%d ", num % 10); } int main() { int num = 0; scanf("%d", &num); Print(num); return 0; }

运行截图：

三、递归与迭代

3.1斐波那契数列（递归）

斐波那契数列定义：数列前两项均为 1，从第三项起，每一项都等于其相邻前两项之和。

前十个斐波那契数： 1 1 2 3 5 8 13 21 34 55

斐波那契数列公式：

看到这个公式，我们很容易写出递归代码：

int Fib(int n) { if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 2); }

代码测试：

#include <stdio.h> #include <time.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() { time_t start_time = time(NULL); int use_time =time(NULL) - start_time; printf("当前使用的时间：%d\n", use_time); int n = 0; printf("请输入想要查询的斐波那契数："); scanf("%d", &n); int ret=Fib(n); printf("%d\n", ret); printf("计算算第三个斐波那契数时一共计算了多少次:%d\n", count); int total_time = time(NULL) - start_time; printf("总共使用的时间：%d\n", total_time); return 0; }

输入10，运行截图：

可见第10个斐波那契数是55，总共只花了一秒计算得出

输入50，运行截图：

可以发现，当我们查询第50个斐波那契数时，我们用了52秒的时长，程序执行了非常长的时间，而且最终计算得到的结果还是错误滴

我们再来看看代码中计算第40个斐波数时，我们第三个斐波数一共计算了多少次

我们在上方的代码中，加入了一个记数的代码，计第三个斐波那契数一共计算了多少次

输入40，运行截图：

可以看到，光是第三个斐波那契数，我们就计算了39088169次，这说明用此递归写斐波那契数列的代码是非常低效的，代码的递归层次越深，冗余的计算就越多，重复计算就越多，所以递归在使用的时候，要注意效率问题，递归虽然代码简单，能很快写出将复杂代码简化的代码，但需要考虑大量重复计算调用函数的效率和栈溢出等问题

为啥会出现多次计算同一个斐波那契数的情况呢？

我们来看看计算第六个斐波那契数时的计算情况：

如图所示，我们会把fib（6）拆分成fib（5）和fib（4），然后将fib（5）和fib（4）又会分别拆分计算，可以看到，光是计算fib（6），我们都要计算二的三次方次为8次；再者，当我们计算fib（8）时，它首先拆分成7和6，7又可以拆成6和5，这里就两个fib（6）了，光fib（6），我们就要计算十六次，不敢想象，当计算fib（40）时，光一个fib（6）就要计算多少次多少时间，这样子的效率是非常低下的，更别说计算fib（40）了

所以我们可以考虑下迭代的方式去写递归

3.2斐波那契数列（迭代）

迭代的思想就是通过利用循环，从已知初始值开始，一层一层向上递推、逐步累加，一步步算出结果。

迭代代码：

#include <stdio.h> int Fib(int n) { if (n <= 2) return 1; else { int a = 1, b = 1; int z = 0; while (n > 2) { z = a + b; // 算出下一个新数 a = b; // 旧后数前移，变成前一个数 b = z; // 新数接班，变成后一个数 n--; } return z; } }

已知斐波那契数第一个数和第二个数都是1，所以我们把1赋值给变量a和b，a表示第一个数，b表示第二个数，当n<=2时，就直接return1，当算n=3：第三个斐波那契数时只需计算a+b得到的结果，就是第三个数了，只用计算一次，所以while循环只需要1次；算第四个数时，我们再把刚刚算出第三个斐波那契数的值赋给b，把原来的b的值赋给a，再相加，也就是第二个斐波那契数加上了第三个斐波那契数，这样就得到了第四个斐波那契数，while循环要执行两次。这样就是一次递推，舍去第一个数，后面的数往前走，然后再相加获得新的数，算第五个斐波数时，就要循环三次，所以根据规律，循环次数＝n-2，所以我们每次循环完都n--，2是固定死的，当减到2时就退出循环，就能刚好对应我们想要循环的次数，也就是n＞2和n-- 两者配合，作为我们循环的条件

总结：数总体往前挪，递推求下一项

这样的话就无重复计算，效率高效

测试代码：

int main() { time_t start_time = time(NULL); int n = 0; printf("请输入想要查询的斐波那契数："); scanf("%d", &n); int ret=Fib(n); printf("%d\n", ret); printf("计算算第三个斐波那契数时一共计算了多少次:%d\n", count); int total_time = time(NULL) - start_time; printf("总共使用的时间：%d\n", total_time); return 0; }

运行截图：

可以看到效率非常高，结果错误是因为int存不下那么大的数，二进制中最高位符号位被挤成1，所以变成了负数，C 语言标准里，有符号整数溢出的结果是未定义的，所以我们不用管为啥溢出后变成这个数，不同编译器对整数溢出部分的处理结果会有差异，得到的数也不一样

四、最终的总结

• 迭代：由小 → 到大，正向递推，循环实现，无重复计算，效率高
• 朴素递归：由大 → 到小，再由小 → 到大，层层拆分，自己调用自己，大量重复计算，效率极低