铁汁们，递归（下）已经更新咯，欢迎铁汁们批评指正。
蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（下）_安然无虞的博客-CSDN博客
目录
欢迎回到：遇见蓝桥遇见你，不负代码不负卿！
【声明】：为了让更多的铁汁理解递归，笔者在前面的引入部分赘述可能过长，请铁汁们多点耐心哦，后面有大招。
【前言】：很多人都认为“递归”是语言学习中最难理解的内容之一，当然笔者也是这么认为的，哈哈，但是既然笔者已经将文章发布出来了，自然是有了充分的准备，所以，铁汁们不用紧张，看到最后你会发现，递归其实是一个很自然的东西。
一、递归是什么？
递归是一种应用非常广泛的算法（或者编程技巧）。之后我们要讲的很多数据结构和算法的编码实现都要用到递归，比如 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! 用递归法编写程序实现如下：
#include<stdio.h> int factor(int n) { if (n == 1) { return 1; } return n * factor(n - 1); } int main() { int n = 5; int ret = factor(n); printf("%d\n", ret); return 0; }
注意：本题就是简单了解一下用递归写程序是什么样，重点讲解放在后面。
提示：C语言支持递归，即函数可以直接或者间接的调用自己。但是要格外注意为递归函数编写终止条件，否则将产生无限循环。
总结一下：写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
虽然我讲了这么多方法，但是作为初学者，现在是不是还是有种想不太清楚的感觉呢？这也是文章开头我说递归代码比较难理解的原因所在。那怎么办呢，请继续看...
三、怎么玩转递归
在重复中找变化，在变化中找重复！
1、大招：递归“三段论式”设计经验
- 找重复-->找子问题
- 找变化-->找重复中的变化量作为参数
- 找边界-->找参数变化趋势设计出口
注意：
- 对于递归这种折磨人的知识，有人两三天就会了，有人三五年也不会。主要看你悟不悟得透，能不能找到对于递归的感觉。
- 三段论中的找重复，这个步骤是最重要而且还是最需要感觉的，不过你要相信Practice makes prefect！踏踏实实，多做，多练，多敲。
- 在找边界设计出口时，最好写在函数的开头。
2、练习策略
- 循环改递归解题
- 经典递归讲解
- 大量练习，总结规律，掌握套路
- 找到感觉，挑战高难度
四、精选练习题讲解
1、求n的阶乘
注意：为了方便大家伙的理解，本题没有考虑n == 0的情况
三段论：
- 找重复：n * (n - 1)的阶乘，求(n - 1)的阶乘是原问题的重复，规模更小，是原问题的子问题。
- 找变化：找重复中的变化的量作为参数。本题中很明显是n在变化，所以函数定义过程中的形参是n.
- 找边界：也就是出口的判断，什么时候让函数停止。显然本题中当n == 1时结束。
代码执行
#include<stdio.h> //本题中的变化量是n，所以用作形式参数 int factor(int n) { //出口的判断，最好写在函数的开头，本题中当n == 1时就意味着到边界了，应该终止程序 if (n == 1) { return 1; } //(n - 1)的阶乘是原问题的重复，是其子问题，规模更小 return n * factor(n - 1); } int main() { int n = 5; int ret = factor(5); printf("%d\n", ret); return 0; }
注意：为了言简意赅，本题中没有考虑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是函数的边界
代码执行
//递归求1+2+3+...+10 #include<stdio.h> //很显然num是不断变化的，所以用作函数的形参 int sum(int num) { //找边界 if (num == 1) { return 1; } //1~(num - 1)是原问题的重复，规模更小，是原问题的子问题 return num + sum(num - 1); } int main() { int n = 10; int ret = sum(n); printf("%d\n", ret); return 0; }
3、返回各位数字之和
题目描述：输入一个非负整数，返回组成它的数字之和，如输入1729，应该返回1+7+2+9的值，当然1+7+2+9 == 9+2+7+1，也就是19
三段论
找重复：求（num / 10）组成它的数字之和是原问题的重复，规模更小，是其子问题
找变化：num一直在变化
找边界：num < 10
代码执行
#include<stdio.h> int sum(int num) { if (num < 10) { return num; } return num % 10 + sum(num / 10); } int main() { int num = 1729; printf("%d\n", sum(num)); return 0; }
4、按顺序打印整数i~j
三段论
找重复：（i + 1）是原问题的重复，规模更小，是其子问题
找变化：i 和 j，i在变化不难看出，但为什么要加上j呢，j虽然没有变化，但是i~j这个整体在变，‘i’ 到'j' 的距离不断缩小，所以要加上j来衡量它们二者之间的变化
找边界：当 i > j 时结束
代码执行
#include<stdio.h> void f2(int i, int j) { if (i > j) { return; } printf("%d ", i); f2(i + 1, j); } int main() { f2(2, 9); return 0; }
5、对数组arr所有元素求和
注意：前面内容为了方便更多的铁汁理解，所以笔者选择用C语言编写，但是讲解了4题之后，相信大家对递归都有了一定的认识，数据结构与算法的讲解主要讲的是思路，跟编程语言无关，所以后面的题目笔者选用正在学习中的JAVA语言编写，大家主要听思路，
如果听懂了，自己再用熟练的语言编写程序，那么将会事半功倍！
三段论
找重复：求下标begin + 1到arr.length - 1的元素之和是原问题的重复(将首元素的下边设为begin,JAVA中对数组arr求长度直接用arr.length即可)
找变化：begin和剩下的元素都是在变化的，那么如何衡量begin到数组尾元素之间的变化，所以数组名arr也得用作参数
找边界：当begin == arr.legth - 1,也就是当走到尾时结束。
代码执行
public class Recursion { public static int f3(int[] arr, int begin) { if(begin == arr.length - 1) { return arr[begin]; } return arr[begin] + f3(arr, begin + 1); } public static void main(String[] args) { int[] arr = {1,3,4,6,7,8,9}; int ret = f3(arr, 0); System.out.println(ret); } }
注意：加参数也是设计递归的一个难点，有时候我们就想不明白，为什么“切完“之后不知道怎么去写了，比如这一题，如果形参你只给了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进制的形式，所以再将它还原成十进制数即可。
笔者在这里只给出思路，代码怎么敲，请铁汁们亲自动手实践，用来检测上篇位运算掌握情况。
六、蓝桥结语：遇见蓝桥遇见你，不负代码不负卿
为了让更多的铁汁们能看到这个系列的文章，笔者在这里请求大家动动小手，给笔者来个一键三连，你的支持就是笔者最大的动力，赠人玫瑰，手留余香哦，蟹蟹大家。
铁汁们，递归（下）已经更新咯，快来康康吧。
蓝桥杯算法竞赛系列第二章——深入理解重难点之递归（下）_安然无虞的博客-CSDN博客
![【蓝桥杯】[递归]母牛的故事](https://ucc.alicdn.com/pic/developer-ecology/2is4p5rpji74e_be870067c97c42ca9083c25b149faaa5.png?x-oss-process=image/resize,h_160,m_lfit)