目录一、引例二、递归的概念理解三、递归的简单运用1、求n的阶乘2、顺序打印一个整数的每一位四、递归和迭代的对比——斐波那契数1、什么是斐波那契数2、方法一递归3、方法二迭代循环4、递归和迭代如何取舍五、递归的典型例题1、青蛙跳台阶问题2、汉诺塔问题六、终极目标“扫雷”游戏展开一片前言上一篇详解“扫雷”游戏文章的最后提到了几个拓展功能其中“展开一片”的功能是需要用函数递归的知识去解决的。那么这篇文章我们就来聊一聊这个话题不过这个系列是“C语言入门”系列所以目的不在于用递归去解决多么复杂的问题而是帮助伙伴们更好地理解这个概念以及运用它去解决一些基本问题这里的终级目标就是实现“扫雷”游戏的拓展功能“展开一片”。话不多说我们开始吧一、引例笼统地讲递归可以被总结成一句话函数自己调用自己。先来看一个有意思的程序#include stdio.h int main() { printf(hehe\n); main(); //main函数自己调用自己 return 0; }小伙伴可以猜测一下运行结果。如果你认为是死循环那只说对了一半因为栈溢出Stack overflow的原因程序不会一直运行下去。CtrlF5走起来后大概2秒钟就自动结束。感兴趣的小伙伴可以自己运行试一试这里就只放一张最后的截图其实这个程序就是一个死递归它并没有体现出任何递归的思想放在这里只是先展示一下什么叫“函数自己调用自己”。那么真正用来解决问题的递归又是什么样的一种思想呢二、递归的概念理解这是一张关于递归的“名片”所有的重点都在这里了递归咬文嚼字递递推归回归思想精髓把一个大型复杂问题层层转化为一个与原问题相似但规模较小的子问题来求解直到子问题不能被拆分递归就结束了。总结大事化小的过程必要条件1、递归存在限制条件终止条件当满足这个限制条件的时候递归便不再继续。2、每次递归调用之后越来越接近这个限制条件单凭概念性的文字描述是无法解释清楚的下面我会用两个例子来帮助你进一步认识它。三、递归的简单运用1、求n的阶乘首先我们来复习一下中学数学阶乘的数学公式其实这个数学公式已经很好地展示了什么叫“函数自己调用自己”在没学过递归之前我想迭代循环是一种不错的办法#include stdio.h int Fact(int n) { int result 1; //0和1的阶乘也是1所以初始化为1 for (int i 2;i n;i) { result * i; } return result; } int main() { int n 0; scanf(%d, n); int ret Fact(n); printf(%d\n, ret); return 0; }这确实是一种解决办法但我们现在的目标是用函数递归的方法解决它如何实现呢不妨先来画个示意图假设求5的阶乘根据这个示意图我们再来疏理一遍思路根据递推公式nn*(n-1)能够得出如果要求n!我们必须先求出(n-1)而(n-1)(n-1)*(n-2)!也就是说要求(n-1)我们必须要先求出(n-2)!……仔细想一下会发现这个过程完美印证了上文提到的“把一个大型问题层层转化为一个与原问题相似但规模较小的子问题”。那究竟什么时候是个头呢答直到n0。这里也可以理解为当n0时终于有了一个确切的值递推也就结束了。所以n0就是这个递归的限制条件。如果说递推的过程是“熵增”的过程那么回归就是“熵减”的过程个人感觉很“解压”拿着Fact(0)1这个条件从最小的子问题开始解决一层一层往上最终解决最初的n。理清逻辑之后我们就可以来敲代码啦#include stdio.h int Fact(int n) { if (n 0) return 1; else return Fact(n-1) * n; } int main() { int n 0; scanf(%d, n); int retFact(n); printf(%d\n, ret); return 0; }阶乘就到这里啦下面我们稍微升级一点点难度。2、顺序打印一个整数的每一位不知道小伙伴们前期在学习循环的时候有没有敲过“逆序打印整数”的代码没敲过也不要紧这里先来敲一遍逆序打印的代码#include stdio.h int main() { int m 0; scanf(%d, m); while (m) { printf(%d , m % 10); // %10得到最后一位 m / 10; // /10去掉最后一位 } return 0; }其实逆序打印是一个比较简单的问题但好像一变成顺序打印就提升了一级难度。难在哪里呢就是难在顺序开始时最容易的打印的最后一位被要求最后打印。先来分析一个具体的例子假设现在要顺序打印整数1234该如何去考虑呢不妨把它分成2部分123和44是容易打印的1234%10就可以得到但是在打印4之前要先打印123如何得到1231234/10就可以得到123中3是容易打印的%10但是在打印3之前要先打印12/1012中2是容易打印的%10但是在打印2之前要先打印1/10。文字描述还是过于苍白我们用图示再理解一遍好了接下来就可以试着用代码来实现啦#include stdio.h void Print(int num) { if (num 9) { Print(num / 10); printf(%d , num % 10); } else printf(%d , num % 10); } int main() { int num 0; scanf(%d, num); Print(num); return 0; }其实仔细观察会发现这个自定义函数还可以更加简洁因为if和else里面都有语句“printf(%d , num % 10);”那就意味着只要进入这个自定义函数就要执行这句代码因此可以简化成这样#include stdio.h void Print(int num) { if (num 9) { Print(num / 10); } printf(%d , num % 10); } int main() { int num 0; scanf(%d, num); Print(num); return 0; }好了顺序打印的函数递归到这就结束了。事实上和阶乘一样顺序打印也不是只有递归能解决用迭代的方式也可以的代码如下#include stdio.h void Print(int num) { int arr[32] { 0 }; //取数字只能从个位开始所以迭代解决顺序打印要使用数组存数字 int i 0; do { arr[i] num % 10; //注意这里i先被使用再自增1 num / 10; } while (num); //当num0即最高位被整除掉之时跳出循环 for (int j 0;j i;j) printf(%d , arr[j]); } int main() { int num 0; scanf(%d, num); Print(num); return 0; }既然递归和迭代都能解决问题那到底应该如何取舍呢它们各自有哪些优劣呢四、递归和迭代的对比——斐波那契数我们先分别用递归和迭代的方式去解决一个经典问题求第n个斐波那契数。1、什么是斐波那契数斐波那契数斐波那契数列Fibonacci sequence是这样一个整数序列0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...规律是前两项是 0 和 1从第三项开始每一项都等于前两项之和。数学公式2、方法一递归不知道小伙伴有没有发现解决这个问题函数递归是思路是非常清晰的完全不需要像上面先进行一波逻辑推理和画图分析可能看着数学公式就写出来了不相信小伙伴们可以自己先尝试一下。代码如下#include stdio.h int Fib(int n) { if(n1) return n; else //这个else也可省去不写 return Fib(n - 1) Fib(n - 2); } int main() { int n 0; scanf(%d, n); int retFib(n); printf(%d\n, ret); return 0; }非常简洁的几行代码笔者的个人感觉就是直接把数学公式翻译成C语言代码。现在我们让代码走起来试一下貌似非常顺利那我们再把数字调大一点试试当n50时糟糕我瞬间听到电脑的散热风扇全速运转的声音半分钟之后终于还是算出来了但是这个运算效率确实堪忧啊什么原因导致的呢看图你就明白了我们会发现每次想计算1个斐波那契数都要先计算这个斐波那契数对下来的2个斐波那契数而计算这2个斐波那契数的前提是它们各自对下来的2个斐波那契数这意味着递归层次越深计算量越大。但这么大的计算量真的有意义吗从图中可以看出从Fib(48)开始后面的每个斐波那契数都在被重复计算且递归层次越深冗余计算越多。可以用代码来测试计算Fib(40)的过程中到底计算了多少次Fib(3)#include stdio.h int count 0; //count作为全局变量main函数和自定义函数里就都能用了 int Fib(int n) { if (n 3) count; if (n 1) return n; else return Fib(n - 1) Fib(n - 2); } int main() { int n 0; scanf(%d, n); int ret Fib(n); printf(%d\n, ret); printf(\ncount%d\n, count); return 0; }第3个斐波那契数竟然被计算了39088169次由此可见计算斐波那契数时用递归确实是一种非常不明智的选择。总结递归在形式上比较简洁但在解决某些问题时会产生效率不高。再试试迭代吧看看它的表现如何。3、方法二迭代循环这个问题用迭代的思维去解决就有一定挑战性了。我们先假设求第5个斐波那契数第5个数是“5”它是怎么来的呢是前面的数字一次一次加过来的。现在要用迭代的方式解决也就意味着每一次使用前两个数相加得到第三个数就是一次循环。那一次循环过后呢这三个数字的“身份”应该要发生改变第三个数本来是被加数现在应该变成第二个加数第二个数本来是第二个加数现在应该变成第一个加数而第一个加数已经成功完成了它的“使命”不再参与循环的执行了。还是老规矩上图相信小伙伴们已经搞懂这中间的逻辑了下面就可以敲代码啦#include stdio.h int Fib(int n) { int a 0; int b 1; int c 0; if (n 1) return n; while (n 2) { c a b; a b; b c; n--; } return c; } int main() { int n 0; scanf(%d, n); int ret Fib(n); printf(%d\n, ret); return 0; }很明显迭代在形式上的简洁性不如递归那效率呢让我们聚焦当n50时的运行时间n较小时的运行结果这里就不做展示了和递归的结果无差别按下回车的瞬间总结迭代在逻辑上稍复杂因此形式上不占优势但是实现效率较递归更高既然各有各的优势那么解决问题的时候如果选择呢4、递归和迭代如何取舍事实上我们看到的许多问题是以递归的形式进行解释的如斐波那契数列这只是因为它比非递归的形式更加清晰但是这些问题的迭代实现往往比递归实现效率更高。但当一个问题非常复杂难以使用迭代的方式实现时此时递归实现的简洁性便可以补偿它所带来的运行时开销。总之递归和迭代不存在绝对的谁更好没有非此即彼的标准答案最终怎么选还是要根据实际问题进一步去平衡代码好不好写、跑起来稳不稳定等各种因素。五、递归的典型例题1、青蛙跳台阶问题有一段共n级的台阶一只青蛙想要从最底下跳到最顶端。青蛙一次只有两种跳法要么1次跳1级台阶要么1次直接跳2级台阶。问青蛙跳上这n级台阶一共有多少种不一样的跳法这个问题本质上就是斐波那契数的问题如果我们的思考场景是从下往上跳的过程那么就输了。应该要从最顶端开始往下思考假设青蛙站在第n级台阶那么它的上一跳一定是在第n-1级台阶或者n-2级台阶而它又是如何跳到第n-1级台阶和第n-2级台阶的呢到这里是不是有一种似曾相识的感觉了不过这个问题和单纯的斐波那契数唯一不一样的地方在于初始值。因为青蛙跳台阶问题属于实际问题要根据实际情况来当n1时有1种可能当n2时有2种可能因此青蛙数列斐波那契数列右移一位。敲代码#include stdio.h int frog(int n) { if (n 2) return n; return frog(n - 1) frog(n - 2); } int main() { int n 0; scanf(%d, n); int ret frog(n); printf(%d\n, ret); return 0; }2、汉诺塔问题现有三根柱子A、B、C其中A柱上有n个盘子从下往上依次变大。现要把所有盘子从A移到C并且要求一次只能移动一个盘子且大盘不能压在小盘上打印操作步骤并统计最少需要多少步。示例小伙伴也可以先体验一波游戏汉诺塔游戏网页版https://app-84nri351flkx.appmiaoda.com/如何去思考这个问题呢先来看一张图其实笔者认为n3还是可以一个一个试一下的只是这个图实在有点难画~请大家见谅。但当n4时 如果还是一个一个试那就真的输了因为递归的问题里最怕把问题拆的很细而要用宏观的视角去看问题。试着这样去考虑除了底盘它上面的其他盘子我们看作一个整体。既然要把所有盘子移到C柱那么一定有一步是除了底盘在A柱其他盘子“省略亿点点细节”按顺序叠好在B柱这时候我们把底盘移到C柱再“省略亿点点细节”把其他盘子移到C柱。至于“亿点点细节”则需一层一层参考上一次的过程。如图现在我们试着把每次相似的操作过程提炼成自定义函数函数功能一句话概括打印汉诺塔的操作步骤并统计最少需要多少步核心逻辑第1步其余盘子从起始柱子挪到辅助柱子第2步底盘从起始柱子挪到终点柱子第3步其余盘子从辅助柱子放入终点柱子函数头函数名Hanoi函数原型void Hanoiint n,char from,char aux,char to返回值不需要只需要完成任务即可参数盘子的个数起始柱子中转柱子终点柱子函数体1、其余盘子从起始柱子挪到辅助柱子void Hanoi(int n, char from, char aux, char to) { Hanoi(n - 1, from, to, aux); }2、底盘从起始柱子挪到终点柱子void Hanoi(int n, char from, char aux, char to) { Hanoi(n - 1, from, to, aux); printf(%c - %c\n, from, to); }3、其余盘子从辅助柱子放入终点柱子void Hanoi(int n, char from, char aux, char to) { Hanoi(n - 1, from, to, aux); printf(%c - %c\n, from, to); Hanoi(n - 1, aux, from, to); }4、限制条件当只有1个盘子时void Hanoi(int n, char from, char aux, char to) { if (n 1) { printf(%c - %c\n,from,to); return; } Hanoi(n - 1, from, to, aux); printf(%c - %c\n, from, to); Hanoi(n - 1, aux, from, to); }5、计数int count 0; //全局变量累计步数 void Hanoi(int n, char from, char aux, char to) { if (n 1) { printf(%c - %c\n,from,to); count; //注意这一步计数很容易遗忘 return; } Hanoi(n - 1, from, to, aux); printf(%c - %c\n, from, to); count; Hanoi(n - 1, aux, from, to); }把主函数加上检验一下#include stdio.h int count 0; void Hanoi(int n, char from, char aux, char to) { if (n 1) { printf(%c - %c\n,from,to); count; return; } Hanoi(n - 1, from, to, aux); printf(%c - %c\n, from, to); count; Hanoi(n - 1, aux, from, to); } int main() { int n 0; printf(请输入盘子数量); scanf(%d, n); Hanoi(n, A, B, C); printf(共%d步\n, count); return 0; }好了汉诺塔问题就告一段落了的确是一个很有意思的问题值得反复回味~六、终极目标“扫雷”游戏展开一片前面铺垫了那么多终于来到了我们的终极目标不知道小伙伴们还记不记得“扫雷”游戏是怎么实现的。忘了的话可以先去复习一下C语言入门 | “扫雷”小游戏 保姆级详解容易想到的是展开一片的功能一定嵌套在FindMine函数里因此这里先贴上FineMine函数void FindMine(char mine[ROWS][COLS], char show[ROWS][COLS], int r, int c) { int x 0; int y 0; int win 0; while (winr*c- EASY_COUNT) { printf(请输入要排查的坐标); scanf(%d%d, x, y); if (x 1 x r y 1 y c) { if (show[x][y] ! *) printf(该坐标已经被排查过请不要重复排查\n); else { if (mine[x][y] 1) { printf(很遗憾你被炸死了\n); DisplayBoard(mine, ROW, COL); break; } else { size_t count GetMineCount(mine, x, y); show[x][y] (char)count0; DisplayBoard(show, ROW, COL); win; } } } else { printf(输入错误请重新输入); } } if (win r * c - EASY_COUNT) { printf(恭喜你排雷成功\n); } }现在我们来思考有展开一片功能的函数Expand它会放在哪里呢这个问题很容易想到一定是在打印棋盘之前。并且Expand函数可以替换掉前面两句代码如果这一点暂时想不到的话也不要紧不如先假设是这样等后面你就会恍然大悟了。else { //Expand函数 DisplayBoard(show, ROW, COL); win; }接下来就该自定义这个函数了函数功能一句话概括输入 (x, y) 坐标若周围无雷则向四面八方连片展开直到碰到有雷的边界为止。核心逻辑第1步校验坐标合法性越界直接放弃递归产生的邻居可能出界第2步校验是否已翻开翻过就不再处理第3步用GetMineCount函数计算(x,y)周围8格的雷的数量count第4步把(x,y)上count存入showcount0存0count 0存数字字符第5步判断countcount0对8个邻居重复上述流程递归count 0只显示数字不再递归函数头函数名Expand函数原型int Expand(char mine[ROWS][COLS],char show[ROWS][COLS],int x,int y)参数mine数组show数组坐标x坐标y返回值本次总共新翻开了多少个格子自己 所有被递归展开的格子函数体1、校验坐标合法性static int Expand(char mine[ROWS][COLS], char show[ROWS][COLS], int x, int y) { if (x1 || y1 || xROW || yCOL) return 0; }2、校验是否已翻开static int Expand(char mine[ROWS][COLS], char show[ROWS][COLS], int x, int y) { if (x1 || y1 || xROW || yCOL) return 0; if(show[x][y]!*) return 0; //上面2条语句是递归的限制条件 }3、用GetMineCount函数计算(x,y)周围8格的雷的数量countstatic int Expand(char mine[ROWS][COLS], char show[ROWS][COLS], int x, int y) { if (x1 || y1 || xROW || yCOL) return 0; if(show[x][y]!*) return 0; //上面2条语句是递归的限制条件 int count GetMineCount(mine, x, y); }4、把(x,y)上count存入showstatic int Expand(char mine[ROWS][COLS], char show[ROWS][COLS], int x, int y) { if (x1 || y1 || xROW || yCOL) return 0; if(show[x][y]!*) return 0; //上面2条语句是递归的限制条件 int count GetMineCount(mine, x, y); show[x][y]count 0 ? 0 : (char)(count)0; //灵活运用三目运算符 }5、判断countstatic int Expand(char mine[ROWS][COLS], char show[ROWS][COLS], int x, int y) { if (x1 || y1 || xROW || yCOL) return 0; if(show[x][y]!*) return 0; //上面2条语句是递归的限制条件 int count GetMineCount(mine, x, y); show[x][y]count 0 ? 0 : (char)(count)0; int n 1; //至少会翻1个格子 if (count 0) { n Expand(mine, show, x - 1, y - 1); n Expand(mine, show, x - 1, y); n Expand(mine, show, x - 1, y 1); n Expand(mine, show, x , y - 1); n Expand(mine, show, x , y 1); n Expand(mine, show, x 1, y - 1); n Expand(mine, show, x 1, y); n Expand(mine, show, x 1, y 1); } return n; }那么FindMine函数那里的复合语句该怎么变动呢else { winExpand(mine, show, x, y); DisplayBoard(show, ROW, COL); }OK这篇文章的内容到此就结束了感谢观看欢迎评论区交流讨论完