【C语言】函数递归(含扫雷进阶思路)

一、什么是递归

    递归是学习C语⾔函数绕不开的⼀个话题，那什么是递归呢？     递归其实是⼀种解决问题的⽅法，在C语⾔中，递归就是函数⾃⼰调⽤⾃⼰。 写⼀个史上最简单的C语⾔递归代码：

    上述就是⼀个简单的递归程序，只不过上⾯的递归只是为了演⽰递归的基本形式，不是为了解决问题，代码最终也会陷⼊死递归，导致栈溢出，因为代码每执行完printf时，又调用了main函数，也就是又从main函数的头开始，然后再打印，最后一陷入死递归，如果代码突然结束，可能就是程序一直在创建函数栈帧，导致了栈溢出

二、递归的使用思路和限制条件

1.递归的使用思路

    把⼀个⼤型复杂问题层层转化为⼀个与原问题相似，但规模较⼩的⼦问题来求解；直到⼦问题不能再被拆分，递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程     递归中的递就是递推的意思，归就是回归的意思，现在不懂没关系，接下来慢慢来体会

2.递归的限制条件

递归在书写的时候，有2个必要条件：     • 递归存在限制条件，当满⾜这个限制条件的时候，递归便不再继续，如果没有限制，可能会陷入死递归     • 每次递归调⽤之后越来越接近这个限制条件。 在下⾯的例⼦中，我们逐步体会这2个限制条件

三、递归的举例

举例1：求n的阶乘

    ⼀个正整数的阶乘（factorial）是所有⼩于及等于该数的正整数的积，并且0的阶乘为1。 ⾃然数n的阶乘写作n! （1）我们知道n的阶乘的公式： n！ = n ∗ (n − 1)! 如：

      5! = 5*4*3*2*1
      4! = 4*3*2*1
   //所以:5! = 5*4!

    这样的思路就是把⼀个较⼤的问题，转换为⼀个与原问题相似，但规模较⼩的问题来求解的     当 n==0 的时候，n的阶乘是1，其余n的阶乘都是可以通过公式计算 （2）n的阶乘的递归公式如下：

    所以我们可以在函数fact中调用fact函数，实现递推，每次递推n都减1，直到n等于0，随后函数开始返回，最后算出n的阶乘，如：

运行结果：

（3）画图整个过程演示：

2.举例2：顺序打印⼀个整数的每⼀位

    输⼊⼀个整数m，按照顺序打印整数的每⼀位 比如：

输⼊：1234 输出：1 2 3 4
输⼊：520  输出：5 2 0

（1）分析：     这个题⽬，放在我们⾯前，⾸先想到的是，怎么得到这个数的每⼀位呢？     如果n是⼀位数，n的每⼀位就是n⾃⼰，n是超过1位数的话，就得拆分每⼀位     拆分的方法之前也讲到过，就是%10可以得到最后一位，/10可以去掉最后一位，但是我们要按照顺序打印，一个思路就是直接按上面的方法处理，然后再将它倒着打印即可，我们接下来将的是使用递归的思路     想要用递归解决这个问题，那么我们就要明白使用递归的方法思路，也就是将一个大的问题逐步的化解为一个又一个的小问题，先递推，然后到了某种条件再回归，最后帮我们实现任务     比如我们现在有一个函数叫print，它的作用就是帮我们将一个整数的每一位给打印出来，假如打印1234的每一位，那么就可以拆分成print(123) + print(4)，然后print(123)又可以拆分为print(12) + print(3)，以此类推，如下：

 Print(1234)
==>Print(123) + printf(4)
==>Print(12) + printf(3)
==>Print(1) + printf(2)
==>printf(1) 

    那么递归如何结束呢？我们可以思考，什么情况下函数无需再次递归，没错，就是当这个数只剩下一位数的时候，我们就可以直接将它打印出来，无需递归，那么怎么判断这个数是不是一位数呢？我们就可以将9这个界限找出来，如果一个整数大于9那么它肯定不是一位数，反之它就是个一位数，现在限制条件也清楚了，这个代码也就迎刃而解了

（2）代码实现以及运行结果：

    在这个解题的过程中，我们就是使⽤了⼤事化⼩的思路，把print(1234) 打印1234每⼀位，拆解为⾸先print(123)打印123的每⼀位，再打印得到的4     把print(123) 打印123每⼀位，拆解为⾸先print(12)打印12的每⼀位，再打印得到的3 直到Print打印的是⼀位数，直接打印就⾏

（3）画图演示：

四、递归与迭代对比

    递归是⼀种很好的编程技巧，但是和很多技巧⼀样，也是可能被误⽤的，就像举例1⼀样，看到推导的公式，很容易就被写成递归的形式：

    在C语⾔中每⼀次函数调⽤，都需要为本次函数调⽤在内存的栈区，申请⼀块内存空间来保存函数调⽤期间的各种局部变量的值，这块空间被称为运⾏时堆栈，或者函数栈帧     函数不返回，函数对应的栈帧空间就⼀直占⽤，所以如果函数调⽤中存在递归调⽤的话，每⼀次递归函数调⽤都会开辟属于⾃⼰的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间     所以如果采⽤函数递归的⽅式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出（stack overflow）的问题，关于函数栈帧的创建与销毁的详细过程，会在以后的视频进行讲解     如果不想使⽤递归，就得想其他的办法，通常就是迭代的⽅式（通常就是循环的⽅式） ⽐如：计算 n 的阶乘，也是可以产⽣1~n的数字累计乘在⼀起的，如图：

    上述代码是能够完成任务，并且效率是⽐递归的⽅式更好的     事实上，我们看到的许多问题是以递归的形式进⾏解释的，这只是因为它⽐⾮递归的形式更加清晰，但是这些问题的迭代实现往往⽐递归实现效率更⾼。     当⼀个问题⾮常复杂，难以使⽤迭代的⽅式实现时，此时递归实现的简洁性便可以补偿它所带来的运⾏时开销。

五、递归与迭代对比举例

需求：求第n个斐波那契数     计算第n个斐波那契数，是不适合使⽤递归求解的，但是斐波那契数的问题通过是使⽤递归的形式描述的，如下：

    看这个形式，很容易又到我们写出递归，如：

    当我们输入50时，代码会停住很久，并且这个时间长到我们无法接受，这就是因为函数fib在递归时，创建的函数栈帧太多了，一直递推，一直返回，并且还伴随着多个重复，导致代码卡在那里，如图：

    其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计算，⽽且递归层次越深，冗余计算就会越多。我们可以作业测试：

运行结果为：

    算出的fib(50)的值超过了int的上限，所以出错了，但是后面count的计数没有问题，可以看到光是算个fib(50)居然就算了5亿多次fib(3)，可见这个代码有多浪费空间，多没有效率，所以这种情况我们可以使用迭代替换，我们知道斐波那契数的前2个数都是1，然后前2个数相加就是第3个数，那么我们从前往后，从⼩到⼤计算就⾏了，如图：

    如果我们再次输入50让它计算，可以看到几乎瞬间就可以得到答案，虽然答案还是会因为超出int最大值而错误，但是至少我们知道这样运行效率很高

六、 递归拓展学习

1. ⻘蛙跳台阶问题
2. 汉诺塔问题

可以尝试自己解决，解析和答案在下期给出，敬请期待!

七、扫雷进阶思路

    在上一篇带着大家写了扫雷基本架构，算是简单实现了扫雷的玩法，但是还是有很多缺陷，比如不能标记，在排查坐标周围没有雷，不能扩展的等等问题     但是实际上现在我们已经有能力实现这些需求，比如标记，我们可以在用户排完坐标后进行询问是否标记雷，然后用某个符号代替标志，比如排查坐标周围没有雷时，可以进行扩展，这不就跟我们今天学习的递归紧密相连吗？将扩展一片没有雷的区域，化小为某个坐标扩展加上其它坐标扩展，反复递推，然后回归，我们学的递归就很有用了     现在我们学习了递归，在这里我给出思路，希望友友们可以通过自己的思考将扫雷篇章的那些扩展写出来，当然，我会在下一篇总体出一个扫雷进阶的实现，敬请期待吧！