蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（上）
source link: https://blog.csdn.net/weixin_57544072/article/details/120836167
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（上）
铁汁们，递归（下）已经更新咯，欢迎铁汁们批评指正。
https://blog.csdn.net/weixin_57544072/article/details/120917038?utm_source=app&app_version=4.17.0
目录
欢迎回到：遇见蓝桥遇见你，不负代码不负卿！
【声明】：为了让更多的铁汁理解递归，笔者在前面的引入部分赘述可能过长，请铁汁们多点耐心哦，后面有大招。
【前言】：很多人都认为“递归”是语言学习中最难理解的内容之一，当然笔者也是这么认为的，哈哈，但是既然笔者已经将文章发布出来了，自然是有了充分的准备，所以，铁汁们不用紧张，看到最后你会发现，递归其实是一个很自然的东西。
一、递归是什么？
递归是一种应用非常广泛的算法（或者编程技巧）。之后我们要讲的很多数据结构和算法的编码实现都要用到递归，比如 DFS 深度优先搜索、前中后序二叉树遍历等等。所以，搞懂递归非常重要，否则，后面复杂一些的数据结构和算法学起来就会比较吃力。
不过，别看我说了这么多，递归本身可是一点儿都不“高冷”，咱们生活中就有很多用到递归的例子。说一个笔者小时候经常听到的故事：从前有座山，山上有座庙，庙里有个老和尚在讲故事，讲的什么呢，从前有座山...哈哈，这不就是递归吗，只不过是一个无限递归，原因是没有设置终止条件。
举个栗子：周末你带着女朋友去电影院看电影，女朋友问你，咱们现在坐在第几排啊？电影院里面太黑了，看不清，没法数，现在你怎么办？
别忘了你是程序员，这个可难不倒你，递归就开始派上用场了。于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说他在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他自己在哪一排，于是你就知道答案了。
这就是一个非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。刚刚这个生活中的例子，我们用递推公式将它表示出来就是这样的：
f(n) = f(n-1) + 1 其中，f(1)=1
f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排数，f(1)=1 表示第一排的人知道自己在第一排。
二、如何理解“递归”？
1、递归定义
刘汝佳老师的关于算法竞赛入门经典（紫书）中是这么定义的：
递归：参见“递归”
什么？这个定义什么也没有说啊！好吧，改一下：
递归：如果还是没有明白递归是什么意思，参见“递归”。
奥，也许这次你明白了，原来递归就是自己用到自己的意思。这个定义显然比上一个好些，因为当你终于悟出其中到道理后，就不用继续“参见”下去了。事实上，递归的含义比这个要广泛。
A经理：“这事不归我管，去找B经理。” 于是你去找B经理。
B经理：“这事不归我管，去找A经理。”于是你又回到了A经理这儿。
接下来发生的事就不难想到了。只要两个经理的说辞不变，你有始终听话，你将会永远往返于两个经理之间。这叫做“无限递归”。尽管在这里，A经理并没有让你找他自己，但还是回到了他这儿。换句话说，“间接用到了自己” 也算递归。
回忆一下，在小学的时候，正整数是如何定义的？正整数1,2,3......这些数。这样的定义也许对于小学生来说是没有任何问题的，但当你觉得这样定义“不太严密”时，你或许会喜欢这样的定义：
（1）1是正整数。
（2）如果n是正整数，那么n + 1也是正整数。
（3）只有通过（1）、（2）定义出来的才是正整数。（这里牺牲一点严密性，换来的是更通俗易懂的表达方式）
这样的定义为什么说成是递归呢，因为在“正整数“还没有定义完时，就用到了”正整数”的定义。其实这和前面“参见递归”在本质上是相同的，只是没有它那么直接和明显。
2、递归需要满足的三个条件
究竟什么样的问题可以用递归来解决呢？我总结了三个条件，只要同时满足以下三个条件，就可以用递归来解决。
1. 一个问题的解可以分解为几个子问题的解
何为子问题？子问题就是数据规模更小的问题。比如，前面讲的电影院的例子，你要知道，“自己在哪一排”的问题，可以分解为“前一排的人在哪一排”这样一个子问题。
2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
比如电影院那个例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一样的。
3. 存在递归终止条件
把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件。
3、递归函数
数学函数也可以递归定义，例如，阶乘函数f(x) = n! 用递归法编写程序实现如下：
注意：本题就是简单了解一下用递归写程序是什么样，重点讲解放在后面。
提示：C语言支持递归，即函数可以直接或者间接的调用自己。但是要格外注意为递归函数编写终止条件，否则将产生无限循环。
总结一下：写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
虽然我讲了这么多方法，但是作为初学者，现在是不是还是有种想不太清楚的感觉呢？这也是文章开头我说递归代码比较难理解的原因所在。那怎么办呢，请继续看...
三、怎么玩转递归
在重复中找变化，在变化中找重复！
1、大招：递归“三段论式”设计经验
- 找重复-->找子问题
- 找变化-->找重复中的变化量作为参数
- 找边界-->找参数变化趋势设计出口
- 对于递归这种折磨人的知识，有人两三天就会了，有人三五年也不会。主要看你悟不悟得透，能不能找到对于递归的感觉。
- 三段论中的找重复，这个步骤是最重要而且还是最需要感觉的，不过你要相信Practice makes prefect！踏踏实实，多做，多练，多敲。
- 在找边界设计出口时，最好写在函数的开头。
2、练习策略
- 循环改递归解题
- 经典递归讲解
- 大量练习，总结规律，掌握套路
- 找到感觉，挑战高难度
四、精选练习题讲解
1、求n的阶乘
注意：为了方便大家伙的理解，本题没有考虑n == 0的情况
- 找重复：n * (n - 1)的阶乘，求(n - 1)的阶乘是原问题的重复，规模更小，是原问题的子问题。
- 找变化：找重复中的变化的量作为参数。本题中很明显是n在变化，所以函数定义过程中的形参是n.
- 找边界：也就是出口的判断，什么时候让函数停止。显然本题中当n == 1时结束。
注意：为了言简意赅，本题中没有考虑n == 0的情况。可能看到这里你还是不能完全理解递归，那么我们应该先理解清楚“上面函数的执行过程”，尤其是，函数执行结束之后，回到调用位置继续往下执行。
注意：建议上面的执行过程，请铁汁们在下面的练习中每一个都画出来，这样你才能清楚地体会到“函数的执行过程”，明白递归的奥秘。
如果仍然无法理解上面的递归，可以作如下比喻。
皇帝（拥有main函数栈帧的男人）：宰相，你给我算一下f(5)。
宰相（拥有f(5)栈帧的男人）：大臣，你给我算一下f(4)。
大臣（拥有f(4)栈帧的男人）：知府，你给我算一下f(3)。
知府（拥有f(3)栈帧的男人）：县令，你给我算一下f(2)。
县令（拥有f(2)栈帧的男人）：师爷，你给我算一下f(1)。
师爷（拥有f(1)栈帧的男人）：回老爷，f(1) = 1。
县令（心算f(2) = 2 * f(1) = 2）回知府大人，f(2) = 2。
知府（心算f(3) = 3 * f(2) = 6）回大人，f(3) = 6。
大臣（心算f(4) = 4 * f(3) = 24）回宰相大人，f(4) = 24。
宰相（心算f(5) = 5 * f(4) = 120）回陛下，f(5) = 120。
皇帝满意极了。
虽然这个比喻不甚恰当，但也可以说明一些问题。函数调用时新建了一个栈帧，并且跳转到了函数的开头去执行，就好比皇帝找宰相、宰相找大臣这样的过程。尽管同一时刻可以有多个栈帧（皇帝、宰相、大臣、县令同时处于“等待下级回话”的状态），但是当前代码行只有一个。
铁汁们如果理解了这个比喻，但是不理解调用栈，没关系，它不是本文重点 ，在后面系列的博文中笔者会做详细介绍。你只需要知道递归为什么能正常工作即可。设计递归程序的重点在于上级给下级安排工作。
此时此刻，是补充第一种解题思维——“切蛋糕思维”，最好的时机
如果一时不是很明白，没有关系，后面还有大量的练习让铁汁们体会这个思维的美妙。
2、递归求1+2+...+10
找重复：求1~(num - 1)是原问题的重复，规模更小，是原题的子问题
找变化：很显然，num是不断变化的，所以函数的形参是num
找边界：num == 1是函数的边界
3、返回各位数字之和
题目描述：输入一个非负整数，返回组成它的数字之和，如输入1729，应该返回1+7+2+9的值，当然1+7+2+9 == 9+2+7+1，也就是19
找重复：求（num / 10）组成它的数字之和是原问题的重复，规模更小，是其子问题
找变化：num一直在变化
找边界：num < 10
4、按顺序打印整数i~j
找重复：（i + 1）是原问题的重复，规模更小，是其子问题
找变化：i 和 j，i在变化不难看出，但为什么要加上j呢，j虽然没有变化，但是i~j这个整体在变，‘i’ 到'j' 的距离不断缩小，所以要加上j来衡量它们二者之间的变化
找边界：当 i > j 时结束
5、对数组arr所有元素求和
注意：前面内容为了方便更多的铁汁理解，所以笔者选择用C语言编写，但是讲解了4题之后，相信大家对递归都有了一定的认识，数据结构与算法的讲解主要讲的是思路，跟编程语言无关，所以后面的题目笔者选用正在学习中的JAVA语言编写，大家主要听思路，如果听懂了，自己再用熟练的语言编写程序，那么将会事半功倍！
找重复：求下标begin + 1到arr.length - 1的元素之和是原问题的重复(将首元素的下边设为begin,JAVA中对数组arr求长度直接用arr.length即可)
找变化：begin和剩下的元素都是在变化的，那么如何衡量begin到数组尾元素之间的变化，所以数组名arr也得用作参数
找边界：当begin == arr.legth - 1,也就是当走到尾时结束。
注意：加参数也是设计递归的一个难点，有时候我们就想不明白，为什么“切完“之后不知道怎么去写了，比如这一题，如果形参你只给了begin，那么肯定很难用递归去解本题，所以这个时候你就应该想想，是不是缺参数。当然，实在想不出来，可能就应该换种思维了，可能那题不适用”切蛋糕思维“，后面我们会一一介绍。
五、思考题
看过该系列博文的小伙伴都知道，笔者会在博文的最后布置一道思考题，并且讲解上篇博文的思考题。
今天暂时不布置思考题了，但是有任务哦，就是将斐波那契数列和青蛙跳台阶看一下，下篇博文会详细讲解他们用到的另外一种思维。
在讲解上篇思考题的时候，请大家再浏览一遍上篇博文的大致内容，复习巩固一下。
https://blog.csdn.net/weixin_57544072/article/details/120798996utm_source=app&app_version=4.16.0
题：出现K次与出现1次
数组中只有一个数出现1次，其他的数出现了K次，请输出只出现1次的数。
如2,2,2,8,7,7,7,3,3,3
解这样题目的时候，实在不行，就用暴力求解法--》计数即可
但是既然出现在上篇的博文中，那么一定就是让我们使用位运算解决。
讲思路之前，首先大家需要对一个知识点有所了解，那就是：
两个相同的二进制数做不进位加法，结果为0；
十个相同的十进制数做不进位加法，结果为0；
所以有这么一个结论：K个相同的K进制数做不进位加法，结果为0
明白上面那条结论之后，就可以说解决本题的思路了：先将给定的十进制数转化成K进制，再在每个位上做不进位加法，剩下的那个数就是只出现一次的数，不过暂时是K进制的形式，所以再将它还原成十进制数即可。
笔者在这里只给出思路，代码怎么敲，请铁汁们亲自动手实践，用来检测上篇位运算掌握情况。
六、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿
为了让更多的铁汁们能看到这个系列的文章，笔者在这里请求大家动动小手，给笔者来个一键三连，你的支持就是笔者最大的动力，赠人玫瑰，手留余香哦，蟹蟹大家。
铁汁们，递归（下）已经更新咯，快来康康吧。
https://blog.csdn.net/weixin_57544072/article/details/120917038?utm_source=app&app_version=4.17.0
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK