我所使用的编译器是VS2022目录什么是递归递归的举例递归与迭代最终的总结一、什么是递归递归的编程思想就是函数自己调用自己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*Fact4接着4进去4不是0会执行4*Fact3接着3进去3不是0会执行3*Fact2接着2进去2不是0会执行2*Fact1接着1进去1不是0会执行1*Fact00进去遇到递归终止条件n0此时返回1也就是Fact01开始一层一层回溯开始回溯先回溯到1*Fact0结果为1也就是Fact1为1再回溯到2*Fact1结果为2也就是Fact2为2再回溯到3*Fact2结果为6也就是Fact3为6再回溯到4*Fact3结果为24也就是Fact4为24最后回溯到5*Fact4结果为120然后return返回了最刚开始的5*Fact4的值也就是120总结递归就是分为( 递推回溯 )两个部分从Fact(5)开始根据终止条件往下递推递推到Fact(0)时n0达到终止条件开始往回回溯回到到Fact(5)也就是从哪里开始递推最后就回溯到哪里从哪开始就从哪结束2.2按顺序打印整数的每一位比如输入1234我们要打印出1 2 3 4的效果每个数中间加了空格想要用递归实现这个功能我们可以拆分一下怎么获得这样的效果首先1234我们可以拆分成1234先打印123再打印4再拆成1234先打印12再打印3和4再拆除1234先打印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 retFib(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次这说明用此递归写斐波那契数列的代码是非常低效的代码的递归层次越深冗余的计算就越多重复计算就越多所以递归在使用的时候要注意效率问题递归虽然代码简单能很快写出将复杂代码简化的代码但需要考虑大量重复计算调用函数的效率和栈溢出等问题为啥会出现多次计算同一个斐波那契数的情况呢我们来看看计算第六个斐波那契数时的计算情况如图所示我们会把fib6拆分成fib5和fib4然后将fib5和fib4又会分别拆分计算可以看到光是计算fib6我们都要计算二的三次方次为8次再者当我们计算fib8时它首先拆分成7和67又可以拆成6和5这里就两个fib6了光fib6我们就要计算十六次不敢想象当计算fib40时光一个fib6就要计算多少次多少时间这样子的效率是非常低下的更别说计算fib40了所以我们可以考虑下迭代的方式去写递归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和ba表示第一个数b表示第二个数当n2时就直接return1当算n3第三个斐波那契数时只需计算ab得到的结果就是第三个数了只用计算一次所以while循环只需要1次算第四个数时我们再把刚刚算出第三个斐波那契数的值赋给b把原来的b的值赋给a再相加也就是第二个斐波那契数加上了第三个斐波那契数这样就得到了第四个斐波那契数while循环要执行两次。这样就是一次递推舍去第一个数后面的数往前走然后再相加获得新的数算第五个斐波数时就要循环三次所以根据规律循环次数n-2所以我们每次循环完都n--2是固定死的当减到2时就退出循环就能刚好对应我们想要循环的次数也就是n2和n-- 两者配合作为我们循环的条件总结数总体往前挪递推求下一项这样的话就无重复计算效率高效测试代码int main() { time_t start_time time(NULL); int n 0; printf(请输入想要查询的斐波那契数); scanf(%d, n); int retFib(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 语言标准里有符号整数溢出的结果是未定义的所以我们不用管为啥溢出后变成这个数不同编译器对整数溢出部分的处理结果会有差异得到的数也不一样四、最终的总结迭代由小 → 到大正向递推循环实现无重复计算效率高朴素递归由大 → 到小再由小 → 到大层层拆分自己调用自己大量重复计算效率极低 
长河君 · 2026/11/1 1:32:08 · 阅读 1.2k 0基础C语言积跬步之函数递归
我所使用的编译器是VS2022目录什么是递归递归的举例递归与迭代最终的总结一、什么是递归递归的编程思想就是函数自己调用自己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*Fact4接着4进去4不是0会执行4*Fact3接着3进去3不是0会执行3*Fact2接着2进去2不是0会执行2*Fact1接着1进去1不是0会执行1*Fact00进去遇到递归终止条件n0此时返回1也就是Fact01开始一层一层回溯开始回溯先回溯到1*Fact0结果为1也就是Fact1为1再回溯到2*Fact1结果为2也就是Fact2为2再回溯到3*Fact2结果为6也就是Fact3为6再回溯到4*Fact3结果为24也就是Fact4为24最后回溯到5*Fact4结果为120然后return返回了最刚开始的5*Fact4的值也就是120总结递归就是分为( 递推回溯 )两个部分从Fact(5)开始根据终止条件往下递推递推到Fact(0)时n0达到终止条件开始往回回溯回到到Fact(5)也就是从哪里开始递推最后就回溯到哪里从哪开始就从哪结束2.2按顺序打印整数的每一位比如输入1234我们要打印出1 2 3 4的效果每个数中间加了空格想要用递归实现这个功能我们可以拆分一下怎么获得这样的效果首先1234我们可以拆分成1234先打印123再打印4再拆成1234先打印12再打印3和4再拆除1234先打印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 retFib(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次这说明用此递归写斐波那契数列的代码是非常低效的代码的递归层次越深冗余的计算就越多重复计算就越多所以递归在使用的时候要注意效率问题递归虽然代码简单能很快写出将复杂代码简化的代码但需要考虑大量重复计算调用函数的效率和栈溢出等问题为啥会出现多次计算同一个斐波那契数的情况呢我们来看看计算第六个斐波那契数时的计算情况如图所示我们会把fib6拆分成fib5和fib4然后将fib5和fib4又会分别拆分计算可以看到光是计算fib6我们都要计算二的三次方次为8次再者当我们计算fib8时它首先拆分成7和67又可以拆成6和5这里就两个fib6了光fib6我们就要计算十六次不敢想象当计算fib40时光一个fib6就要计算多少次多少时间这样子的效率是非常低下的更别说计算fib40了所以我们可以考虑下迭代的方式去写递归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和ba表示第一个数b表示第二个数当n2时就直接return1当算n3第三个斐波那契数时只需计算ab得到的结果就是第三个数了只用计算一次所以while循环只需要1次算第四个数时我们再把刚刚算出第三个斐波那契数的值赋给b把原来的b的值赋给a再相加也就是第二个斐波那契数加上了第三个斐波那契数这样就得到了第四个斐波那契数while循环要执行两次。这样就是一次递推舍去第一个数后面的数往前走然后再相加获得新的数算第五个斐波数时就要循环三次所以根据规律循环次数n-2所以我们每次循环完都n--2是固定死的当减到2时就退出循环就能刚好对应我们想要循环的次数也就是n2和n-- 两者配合作为我们循环的条件总结数总体往前挪递推求下一项这样的话就无重复计算效率高效测试代码int main() { time_t start_time time(NULL); int n 0; printf(请输入想要查询的斐波那契数); scanf(%d, n); int retFib(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 语言标准里有符号整数溢出的结果是未定义的所以我们不用管为啥溢出后变成这个数不同编译器对整数溢出部分的处理结果会有差异得到的数也不一样四、最终的总结迭代由小 → 到大正向递推循环实现无重复计算效率高朴素递归由大 → 到小再由小 → 到大层层拆分自己调用自己大量重复计算效率极低