1. 什么是递归递归是编程中的一种技术指的是一个函数在其定义内部调用自身。递归一定是依赖于函数的。史上最简单的递归程序#includestdio.hintmain(){printf(hehe\n);main();//main函数自己调用自己return0;}这个程序是函数递归但是是错误的递归程序因为会导致死递归最终出现栈溢出的现象。1.1 递归的解释可以把它理解为俄罗斯套娃或镜子中的镜子。把一个大型复杂问题层层转化为一个与原问题相似但规模较小的子问题来求解直到子问题不能再被拆分递归就结束了。大事化小1.2 递归的核心要素一个正确的递归函数必须包含两个关键部分递归调用递推阶段函数自己调用自己每次调用时问题的规模都应该比上一次更小逐步逼近一个最简单的基础情况。终止条件基础情况一个不再进行递归调用、能直接返回结果的特定条件。如果没有终止条件递归会无限进行下去最终导致栈溢出错误。2. 递归举例2.1 举例1求n的阶乘题目计算正整数n的阶乘不考虑溢出假设计算机结果在int的取值范围内。一个正整数的阶乘factorial是所有小于及等于该数的正整数的积并且0的阶乘为1。自然数n的阶乘写作n!0! 1 1! 1 2! 2 * 1 3! 3 * 2 * 1 4! 4 * 3 * 2 * 1 5! 5 * 4 * 3 * 2 * 1 5 * 4!2.1.1 分析和代码实现有了上面的概念我们很容易想到n的阶乘的递归公式如下n! 1, n 0 n! n * (n-1)!, n 1当 n 0 的时候n! n * (n-1)!n!转换成了有关(n-1)!的问题同时(n-1)!和n!是相似的问题同时规模在变小当n在不断变小的过程中当n0的时候就不再递归0!就是1。这就是典型的递归场景这时候我们就写一个函数fact(n)来计算n!再结合上面的公式自然地就能写出下面代码#includestdio.hintFact(intn){if(n0)return1;elsereturnn*Fact(n-1);}intmain(){intn0;scanf(%d,n);intretFact(n);printf(%d\n,ret);return0;}在Fact函数内每次递归调用的时候n会变成n-1逐渐变小逼近 n0 这个终止条件递归就结束了。2.1.2 画图推演当n5求5!时递推和回归过程的演示Fact(5) 5 * Fact(4) 5 * 4 * Fact(3) 5 * 4 * 3 * Fact(2) 5 * 4 * 3 * 2 * Fact(1) 5 * 4 * 3 * 2 * 1 * Fact(0) 5 * 4 * 3 * 2 * 1 * 1 1202.2 举例2顺序打印一个整数的每一位输入一个正整数m按照顺序打印整数的每一位。比如输入1234 输出1 2 3 4 输入520 输出5 2 02.2.1 分析和代码实现这个题目放在我们面前首先想到的是怎么得到这个数的每一位呢如果 n 是1位数直接打印 n 就行n 是超过1位数的话就得拆分 n 的每一位1234%10就能得到4然后1234/10得到123这就相当于去掉了4然后继续对123%10就得到了3再除10去掉3以此类推不断进行%10和/10操作直到1234的每一位都得到但是这里有个问题就是得到的数字顺序是倒着的。上面的推理中我们发现其实一个数字的最低位是最容易得到的通过%10就能得到。那我们就把最后1位分离出来把一个n位数看做前面的n-1位 最后一位。比如1234拆分为123和4这样就把4位数转化成3位数1位数的问题。这就是递归的大事化小。那我们假设想写一个函数Print来打印n的每一位如下表示Print(n)如果n是1234那Print(1234) 能打印1234的每一位其中1234中的4可以通过%10得到那么 Print(1234) 就可以拆分为两步Print(1234/10) //打印123的每一位printf(1234%10) //打印4完成上述2步那就完成了1234每一位的打印。那么Print(123)又可以拆分为 Print(123/10) printf(123%10)以此类推下去就有Print(1234) Print(123) printf(4) Print(12) printf(3) Print(1) printf(2) printf(1)直到被打印的数字变成一位数的时候就不需要再拆分递归结束。那么代码完成也就比较清楚voidPrint(intn){if(n9){Print(n/10);}printf(%d ,n%10);}intmain(){intm0;scanf(%d,m);Print(m);return0;}在这个解题的过程中我们就是使用了大事化小的思路把 Print(1234) 打印1234每一位拆解为首先 Print(123) 打印123的每一位再打印得到的4把 Print(123) 打印123每一位拆解为首先 Print(12) 打印12的每一位再打印得到的3直到 Print 打印的是一位数直接打印就行。2.2.2 画图推演以1234每一位的打印来推演一下Print(1234) ├─ Print(123) │ ├─ Print(12) │ │ ├─ Print(1) → printf(1) │ │ └─ printf(2) │ └─ printf(3) └─ printf(4)2.3 举例3求第n个斐波那契数斐波那契数列大家都听过下面这个序列就是斐波那契数列0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...斐波那契数列的特点是第0个数是0第1个数是1往后的数字都是前2个数字之和。现在给定一个n的值(n从0开始)计算出第n个斐波那契数不考虑溢出。2.3.1 分析和代码实现在斐波那契数列中只有前2个数字是必须已知的后期的数字都是可以计算得到的。F(n) 0, n 0 F(n) 1, n 1 F(n) F(n-1) F(n-2), n 2根据这个公式轻松就能得到下面的代码#includestdio.hintFib(intn){if(n0)return0;elseif(n1)return1;elsereturnFib(n-1)Fib(n-2);}intmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);return0;}2.3.2 程序性能分析针对上面的代码我们去测试如果n较小的时候程序很正常但是当 n 较大的时候比如 n50 的时候需要很长时间才能算出结果这个计算所花费的时间是我们很难接受的这也说明递归的写法是非常低效的那是为什么呢随着递归不断的展开我们很容易就能发现在递归的过程中会有重复计算而且递归层次越深冗余计算就会越多。我们可以写代码统计一下冗余计算的数据会非常的惊人。#includestdio.hintcount0;intFib(intn){if(n3)//统计第3个斐波那契数被重复计算的次数count;if(n0)return0;elseif(n1)return1;elsereturnFib(n-1)Fib(n-2);}intmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);printf(\ncount %d\n,count);return0;}这里我们看到了使用递归实现的代码在计算第40个斐波那契数的时候第3个斐波那契数就被重复计算了39088169次正是因为这些大量重复的计算让程序的性能很差。那我们看到了第n个斐波那契数的计算使用递归来实现并非最佳的选择递归过程中如果反复计算子问题会导致指数级时间复杂度最终让程序的性能堪忧2.3.3 栈溢出其实递归程序除了可能影响性能之外还会存在栈溢出的风险。在C语言程序中每一次函数调用都需要为本次函数调用在内存的栈区申请一块内存空间来保存函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。函数如果不返回函数对应的栈帧空间就一直占用所以如果函数调用中存在递归调用的话每一次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢出stack overflow的问题。关于函数栈帧的详细内容请看加餐内容《函数栈帧的创建和销毁》章节。#includestdio.hintcount0;voidtest(){count;printf(当前深度: %d\n,count);intbuffer[1000]{0};// 占用栈空间test();// 无限递归}intmain(){test();return0;}2.4 递归和循环我们发现递归程序有可能导致栈溢出问题或者性能的问题那什么解决办法吗通常会把递归程序改造成循环的方式比如2.4.1 求阶乘递归写法intFact(intn){if(n0)return1;elsereturnn*Fact(n-1);}循环写法intFact(intn){inti0;intret1;for(i1;in;i){ret*i;}returnret;}2.4.2 求斐波那契数递归写法intFib(intn){if(n0)return0;elseif(n1)return1;elsereturnFib(n-1)Fib(n-2);}循环写法intFib(intn){inta1;intb1;intc1;while(n2){cab;ab;bc;n--;}returnc;}当然还有一种优化递归程序中栈溢出问题的方法是采用尾递归的方式但是尾递归不一定可靠有兴趣的同学下来可以研究一下。2.4.3 递归和循环的选择我们看到的许多问题是以递归的形式进行解释的这只是因为它比非递归的形式更加清晰但是这些问题的循环实现往往比递归实现效率更高。当一个问题非常复杂难以使用循环的方式实现时此时递归实现的简洁性便可以补偿它所带来的运行时开销。一般情况下递归的深度100层并且不会造成大量冗余计算的时候可以大胆地使用递归写法。当这个问题使用递归解决存在明显缺陷的时候就需要考虑改造成循环的方式。递归经常会使用到树/图遍历、分治算法、回溯算法中大家在后期学习《数据结构和算法》的知识时候再逐步去体会学习。3. 递归拓展学习借助于AI研究搞清楚算法思想尝试自行阅读代码3.1 二分查找的递归实现#includestdio.h// 递归二分查找函数// arr: 有序数组升序// left: 左边界索引// right: 右边界索引// target: 要查找的目标值// 返回值: 找到返回索引未找到返回-1intbinarySearch(intarr[],intleft,intright,inttarget){// 基本情形未找到目标值if(leftright)return-1;// 计算中间索引避免溢出intmidleft(right-left)/2;if(arr[mid]target)// 找到目标值returnmid;elseif(arr[mid]target)// 目标值在左半部分returnbinarySearch(arr,left,mid-1,target);else// 目标值在右半部分returnbinarySearch(arr,mid1,right,target);}// 包装函数简化调用intsearch(intarr[],intsize,inttarget){returnbinarySearch(arr,0,size-1,target);}intmain(){intarr[]{1,3,5,7,9,11,13,15,17,19};intsizesizeof(arr)/sizeof(arr[0]);inttarget;printf(有序数组: );for(inti0;isize;i){printf(%d ,arr[i]);}printf(\n);// 测试查找target7;intresultsearch(arr,size,target);if(result!-1){printf(元素 %d 找到索引为: %d\n,target,result);}else{printf(元素 %d 未找到\n,target);}target10;resultsearch(arr,size,target);if(result!-1){printf(元素 %d 找到索引为: %d\n,target,result);}else{printf(元素 %d 未找到\n,target);}return0;}3.2 汉诺塔问题A柱上有n个盘子要借助于B柱挪到C柱上。挪动的过程中在柱子上要保证上的盘子小下面的盘子大。如果有1个盘子A-C如果有2个盘子A-BA-CB-C如果有3个盘子A-CA-BC-BA-CB-AB-CA-C如果有n个盘子…演示网站https://gallery.selfboot.cn/zh/algorithms/hanoitower#includestdio.h// 汉诺塔递归函数//pos1上的n个盘子借助于pos2移动到pos3上voidhanoi(intn,charpos1,charpos2,charpos3){if(n0)return;// 将上面n-1个圆盘从起始柱移动到辅助柱hanoi(n-1,pos1,pos3,pos2);// 将最大的圆盘从起始柱移动到目标柱printf(%c - %c\n,pos1,pos3);// 将n-1个圆盘从辅助柱移动到目标柱hanoi(n-1,pos2,pos1,pos3);}intmain(){intn0;printf(请输入汉诺塔的层数: );scanf(%d,n);printf(\n移动过程如下\n);hanoi(n,A,B,C);// A为起始柱B为辅助柱C为目标柱return0;}4. 总结递归是C语言中非常重要的编程技术核心在于大事化小的思想。掌握递归需要理解两个关键要素递归调用和终止条件。同时也要认识到递归可能带来的性能问题和栈溢出风险在合适的场景下选择递归或循环实现。
1. 什么是递归递归是编程中的一种技术指的是一个函数在其定义内部调用自身。递归一定是依赖于函数的。史上最简单的递归程序#includestdio.hintmain(){printf(hehe\n);main();//main函数自己调用自己return0;}这个程序是函数递归但是是错误的递归程序因为会导致死递归最终出现栈溢出的现象。1.1 递归的解释可以把它理解为俄罗斯套娃或镜子中的镜子。把一个大型复杂问题层层转化为一个与原问题相似但规模较小的子问题来求解直到子问题不能再被拆分递归就结束了。大事化小1.2 递归的核心要素一个正确的递归函数必须包含两个关键部分递归调用递推阶段函数自己调用自己每次调用时问题的规模都应该比上一次更小逐步逼近一个最简单的基础情况。终止条件基础情况一个不再进行递归调用、能直接返回结果的特定条件。如果没有终止条件递归会无限进行下去最终导致栈溢出错误。2. 递归举例2.1 举例1求n的阶乘题目计算正整数n的阶乘不考虑溢出假设计算机结果在int的取值范围内。一个正整数的阶乘factorial是所有小于及等于该数的正整数的积并且0的阶乘为1。自然数n的阶乘写作n!0! 1 1! 1 2! 2 * 1 3! 3 * 2 * 1 4! 4 * 3 * 2 * 1 5! 5 * 4 * 3 * 2 * 1 5 * 4!2.1.1 分析和代码实现有了上面的概念我们很容易想到n的阶乘的递归公式如下n! 1, n 0 n! n * (n-1)!, n 1当 n 0 的时候n! n * (n-1)!n!转换成了有关(n-1)!的问题同时(n-1)!和n!是相似的问题同时规模在变小当n在不断变小的过程中当n0的时候就不再递归0!就是1。这就是典型的递归场景这时候我们就写一个函数fact(n)来计算n!再结合上面的公式自然地就能写出下面代码#includestdio.hintFact(intn){if(n0)return1;elsereturnn*Fact(n-1);}intmain(){intn0;scanf(%d,n);intretFact(n);printf(%d\n,ret);return0;}在Fact函数内每次递归调用的时候n会变成n-1逐渐变小逼近 n0 这个终止条件递归就结束了。2.1.2 画图推演当n5求5!时递推和回归过程的演示Fact(5) 5 * Fact(4) 5 * 4 * Fact(3) 5 * 4 * 3 * Fact(2) 5 * 4 * 3 * 2 * Fact(1) 5 * 4 * 3 * 2 * 1 * Fact(0) 5 * 4 * 3 * 2 * 1 * 1 1202.2 举例2顺序打印一个整数的每一位输入一个正整数m按照顺序打印整数的每一位。比如输入1234 输出1 2 3 4 输入520 输出5 2 02.2.1 分析和代码实现这个题目放在我们面前首先想到的是怎么得到这个数的每一位呢如果 n 是1位数直接打印 n 就行n 是超过1位数的话就得拆分 n 的每一位1234%10就能得到4然后1234/10得到123这就相当于去掉了4然后继续对123%10就得到了3再除10去掉3以此类推不断进行%10和/10操作直到1234的每一位都得到但是这里有个问题就是得到的数字顺序是倒着的。上面的推理中我们发现其实一个数字的最低位是最容易得到的通过%10就能得到。那我们就把最后1位分离出来把一个n位数看做前面的n-1位 最后一位。比如1234拆分为123和4这样就把4位数转化成3位数1位数的问题。这就是递归的大事化小。那我们假设想写一个函数Print来打印n的每一位如下表示Print(n)如果n是1234那Print(1234) 能打印1234的每一位其中1234中的4可以通过%10得到那么 Print(1234) 就可以拆分为两步Print(1234/10) //打印123的每一位printf(1234%10) //打印4完成上述2步那就完成了1234每一位的打印。那么Print(123)又可以拆分为 Print(123/10) printf(123%10)以此类推下去就有Print(1234) Print(123) printf(4) Print(12) printf(3) Print(1) printf(2) printf(1)直到被打印的数字变成一位数的时候就不需要再拆分递归结束。那么代码完成也就比较清楚voidPrint(intn){if(n9){Print(n/10);}printf(%d ,n%10);}intmain(){intm0;scanf(%d,m);Print(m);return0;}在这个解题的过程中我们就是使用了大事化小的思路把 Print(1234) 打印1234每一位拆解为首先 Print(123) 打印123的每一位再打印得到的4把 Print(123) 打印123每一位拆解为首先 Print(12) 打印12的每一位再打印得到的3直到 Print 打印的是一位数直接打印就行。2.2.2 画图推演以1234每一位的打印来推演一下Print(1234) ├─ Print(123) │ ├─ Print(12) │ │ ├─ Print(1) → printf(1) │ │ └─ printf(2) │ └─ printf(3) └─ printf(4)2.3 举例3求第n个斐波那契数斐波那契数列大家都听过下面这个序列就是斐波那契数列0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...斐波那契数列的特点是第0个数是0第1个数是1往后的数字都是前2个数字之和。现在给定一个n的值(n从0开始)计算出第n个斐波那契数不考虑溢出。2.3.1 分析和代码实现在斐波那契数列中只有前2个数字是必须已知的后期的数字都是可以计算得到的。F(n) 0, n 0 F(n) 1, n 1 F(n) F(n-1) F(n-2), n 2根据这个公式轻松就能得到下面的代码#includestdio.hintFib(intn){if(n0)return0;elseif(n1)return1;elsereturnFib(n-1)Fib(n-2);}intmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);return0;}2.3.2 程序性能分析针对上面的代码我们去测试如果n较小的时候程序很正常但是当 n 较大的时候比如 n50 的时候需要很长时间才能算出结果这个计算所花费的时间是我们很难接受的这也说明递归的写法是非常低效的那是为什么呢随着递归不断的展开我们很容易就能发现在递归的过程中会有重复计算而且递归层次越深冗余计算就会越多。我们可以写代码统计一下冗余计算的数据会非常的惊人。#includestdio.hintcount0;intFib(intn){if(n3)//统计第3个斐波那契数被重复计算的次数count;if(n0)return0;elseif(n1)return1;elsereturnFib(n-1)Fib(n-2);}intmain(){intn0;scanf(%d,n);intretFib(n);printf(%d\n,ret);printf(\ncount %d\n,count);return0;}这里我们看到了使用递归实现的代码在计算第40个斐波那契数的时候第3个斐波那契数就被重复计算了39088169次正是因为这些大量重复的计算让程序的性能很差。那我们看到了第n个斐波那契数的计算使用递归来实现并非最佳的选择递归过程中如果反复计算子问题会导致指数级时间复杂度最终让程序的性能堪忧2.3.3 栈溢出其实递归程序除了可能影响性能之外还会存在栈溢出的风险。在C语言程序中每一次函数调用都需要为本次函数调用在内存的栈区申请一块内存空间来保存函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。函数如果不返回函数对应的栈帧空间就一直占用所以如果函数调用中存在递归调用的话每一次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。如果采用函数递归的方式完成代码递归层次太深就会浪费太多的栈帧空间也可能引起栈溢出stack overflow的问题。关于函数栈帧的详细内容请看加餐内容《函数栈帧的创建和销毁》章节。#includestdio.hintcount0;voidtest(){count;printf(当前深度: %d\n,count);intbuffer[1000]{0};// 占用栈空间test();// 无限递归}intmain(){test();return0;}2.4 递归和循环我们发现递归程序有可能导致栈溢出问题或者性能的问题那什么解决办法吗通常会把递归程序改造成循环的方式比如2.4.1 求阶乘递归写法intFact(intn){if(n0)return1;elsereturnn*Fact(n-1);}循环写法intFact(intn){inti0;intret1;for(i1;in;i){ret*i;}returnret;}2.4.2 求斐波那契数递归写法intFib(intn){if(n0)return0;elseif(n1)return1;elsereturnFib(n-1)Fib(n-2);}循环写法intFib(intn){inta1;intb1;intc1;while(n2){cab;ab;bc;n--;}returnc;}当然还有一种优化递归程序中栈溢出问题的方法是采用尾递归的方式但是尾递归不一定可靠有兴趣的同学下来可以研究一下。2.4.3 递归和循环的选择我们看到的许多问题是以递归的形式进行解释的这只是因为它比非递归的形式更加清晰但是这些问题的循环实现往往比递归实现效率更高。当一个问题非常复杂难以使用循环的方式实现时此时递归实现的简洁性便可以补偿它所带来的运行时开销。一般情况下递归的深度100层并且不会造成大量冗余计算的时候可以大胆地使用递归写法。当这个问题使用递归解决存在明显缺陷的时候就需要考虑改造成循环的方式。递归经常会使用到树/图遍历、分治算法、回溯算法中大家在后期学习《数据结构和算法》的知识时候再逐步去体会学习。3. 递归拓展学习借助于AI研究搞清楚算法思想尝试自行阅读代码3.1 二分查找的递归实现#includestdio.h// 递归二分查找函数// arr: 有序数组升序// left: 左边界索引// right: 右边界索引// target: 要查找的目标值// 返回值: 找到返回索引未找到返回-1intbinarySearch(intarr[],intleft,intright,inttarget){// 基本情形未找到目标值if(leftright)return-1;// 计算中间索引避免溢出intmidleft(right-left)/2;if(arr[mid]target)// 找到目标值returnmid;elseif(arr[mid]target)// 目标值在左半部分returnbinarySearch(arr,left,mid-1,target);else// 目标值在右半部分returnbinarySearch(arr,mid1,right,target);}// 包装函数简化调用intsearch(intarr[],intsize,inttarget){returnbinarySearch(arr,0,size-1,target);}intmain(){intarr[]{1,3,5,7,9,11,13,15,17,19};intsizesizeof(arr)/sizeof(arr[0]);inttarget;printf(有序数组: );for(inti0;isize;i){printf(%d ,arr[i]);}printf(\n);// 测试查找target7;intresultsearch(arr,size,target);if(result!-1){printf(元素 %d 找到索引为: %d\n,target,result);}else{printf(元素 %d 未找到\n,target);}target10;resultsearch(arr,size,target);if(result!-1){printf(元素 %d 找到索引为: %d\n,target,result);}else{printf(元素 %d 未找到\n,target);}return0;}3.2 汉诺塔问题A柱上有n个盘子要借助于B柱挪到C柱上。挪动的过程中在柱子上要保证上的盘子小下面的盘子大。如果有1个盘子A-C如果有2个盘子A-BA-CB-C如果有3个盘子A-CA-BC-BA-CB-AB-CA-C如果有n个盘子…演示网站https://gallery.selfboot.cn/zh/algorithms/hanoitower#includestdio.h// 汉诺塔递归函数//pos1上的n个盘子借助于pos2移动到pos3上voidhanoi(intn,charpos1,charpos2,charpos3){if(n0)return;// 将上面n-1个圆盘从起始柱移动到辅助柱hanoi(n-1,pos1,pos3,pos2);// 将最大的圆盘从起始柱移动到目标柱printf(%c - %c\n,pos1,pos3);// 将n-1个圆盘从辅助柱移动到目标柱hanoi(n-1,pos2,pos1,pos3);}intmain(){intn0;printf(请输入汉诺塔的层数: );scanf(%d,n);printf(\n移动过程如下\n);hanoi(n,A,B,C);// A为起始柱B为辅助柱C为目标柱return0;}4. 总结递归是C语言中非常重要的编程技术核心在于大事化小的思想。掌握递归需要理解两个关键要素递归调用和终止条件。同时也要认识到递归可能带来的性能问题和栈溢出风险在合适的场景下选择递归或循环实现。
，环境配置)
