看到递归就晕？带你理解递归的本质！

账号已注销:
处理递归，核心就是千万不要想子问题的过程，你脑子能处理几层？马上就绕迷糊了。要想子问题的结果，思路就清晰了

【回复】是的，只要代码的边界条件和非边界条件的逻辑写对了，其他的事情交给数学归纳法就好了。也就是说，写对了这两个逻辑，你的代码自动就是正确的了，没必要想递归是怎么一层一层走的。
【回复】以前每次递归 都要把过程逐一弄得清楚明白，画着画着 头就大了，这就是为啥一直有点小恐惧的原因所在。 今天再次学习 注重结果 和 高度，再看到你这句话 醍醐灌顶 豁然开朗！ 怪不得 我是 码农，而人家是领导，思维高度不一样啊 ！
【回复】天勤考研那二傻子就喜欢想子问题过程真是服气
Unsigned__Gunn:
1. 如何思考二叉树相关问题？ - 不要一开始就陷入细节，而是思考整棵树与其左右子树的关系。 2. 为什么需要使用递归？ - 子问题和原问题是相似的，他们执行的代码也是相同的（类比循环），但是子问题需要把计算结果返回给上一级，这更适合用递归实现。 3. 为什么这样写就一定能算出正确答案？ - 由于子问题的规模比原问题小，不断“递”下去，总会有个尽头，即递归的边界条件 ( base case )，直接返回它的答案“归”； - 类似于数学归纳法（多米诺骨牌），n=1时类似边界条件；n=m时类似往后任意一个节点 4. 计算机是怎么执行递归的？ - 当程序执行“递”动作时，计算机使用栈保存这个发出“递”动作的对象，程序不断“递”，计算机不断压栈，直到边界时，程序发生“归”动作，正好将执行的答案“归”给栈顶元素，随后程序不断“归”，计算机不断出栈，直到返回原问题的答案，栈空。 5. 另一种递归思路 - 维护全局变量，使用二叉树遍历函数，不断更新全局变量最大值。

李国绿子:
棒，我一直觉得是否能透彻理解并熟练操作递归，是一个新手是否入门的重要标志。

蒙古卍中单:
递归的本质是堆栈，知道先入后出的逻辑就能理解了

Kylinzhang70:
太NB了，一下就把递归的核心讲明白了。下面说说我的理解： 其实可以把递归过程类比于一个传话游戏，假设每个人只能解码一段密码中的很小部分字符，那要做的就是每个人解码自己会的，把不会的传递给下一个人，如果最后一个人解码成功，那通过不断把答案回给传递给他的人并组装自己解码的部分，等回到第一个人手里整段密码就会全部解开。这就是递归的过程，问题随着传递不断简化，最后一次递归返回的答案回到第一层，已经是一个庞大的问题的最终答案了。想清楚这一点就能明白递归能解决什么问题，一个能不断分解且子问题解法和主问题相似。 能不能递归首先要分析问题，求二叉树最大深度的问题，只需要知道，根节点的左右子树中谁最高，最高的加上1就是树最大深度。那怎么知道左右子树中谁最高？那如果能知道左右子树的左右子树里谁最高，同样再加一就能得到答案。把这个答案返回给上一层，就是根节点的左右子树中谁最高的，加一得到最终答案。可以看到第二层解决的问题和第一层相似，但规模要小。传到最后到叶子节点，往上返回当前高度，最后就是整颗树的高度。

【回复】小美女你太棒了，需要男朋友么，爱死你了[喜欢][喜欢][喜欢][喜欢]
KIDPhantom:
看灵佬写代码真的好舒服啊，几乎不会出错，并且敲代码的节奏也很均匀，这种节奏里面透露出来的思绪清晰真的很有美感。不知道有没有人能懂，我每次写代码都是改来改去，感觉自己没有提前理清思路。

【回复】我也是，写稍微难点的题目就开始补丁摞补丁了，写到最后感觉很混乱，代码和自己的思绪都是。看up的视频之后深感思路清晰实在是太重要了，最喜欢这种想好思路然后一气呵成的感觉了。[妙啊]
【回复】看up之前的视频，还有一个感觉就是up总是能在写代码之前就想清楚了有几种特殊情况，但我总是会漏掉一两种，得debug时才能发现[大哭]还是题目做的太少了
火鸡味锅巴259:
处理递归可以带上点做动规思路，动规核心思路是写递推式，两者在大部分情况下相同点是假设n-1步做好了最后一步怎么做

life_is_live:
复习一下关于递归hh，有好几天没过来打卡了在赶期末考大物和马思的复习😢等21号全部考完之后放假接着[热词系列_打卡]

板烧原味鸡:
老师您好，我在学习dfs的时候，我记得在遍历一个树的时候，在递归前需要判断 if current_node.left is not None或者 if current_node right is not None: 然后递归 ， 为什么这里不需要判断左右节点是否为空呢？？如果 到了一个 空的 节点， 调用函数的话 不是会报错吗？

【回复】这两种写法都可以，我的写法是在代码的开头判断当前节点是否为空。
empty_zen:
二刷 2024/4/30: 独立回答答主问题。 1. 怎么思考二叉树的相关题目？ 答： 二叉树题目解法需要用到递归。 2. 为什么需要递归？ 答：因为二叉树可以用递归来天然定义。 3. 为什么递归是对的？ 答：明确递归关系和终止条件，递归就会正确解出答案。 4. 计算机是怎么执行递归？ 答：是用call stack来表达。 5. 是否还有另外一种递归思路? 答：有，方法一是分解问题思路（自顶向下）。 方法二不直接求答案，直接看答案是如何生成的。 原来答案是按照某个路径，根节点到叶子节点生成。 于是可以传递参数进行递归， 递归（深度优先）遍历整棵树。此时，需要调整终止条件。 思考难度颇高，需要重点掌握。

empty_zen:
00:00 方法一： 分解法 05:57 方法二： 配全局变量的带参数深度优先搜索法： 关键： 递归的时候 1. 传节点 2. 传路径个数（局部答案）， 里边更新全局答案

empty_zen:
00:00 方法一： 分解法 05:57 方法二： 配全局变量的带参数深度优先搜索法

图图在南极:
想问一下两种递归思路有什么不同呢 主要区别在哪里 我理解的是 主要区别在于传递过程中 一种是只传递NODE 本身 而另一种递归在传递NODE 本身还会传递COUNT 等其他变量。 所以如果我们所求涉及到全局变量的更新 第二种递归思路更合适， 但是如果不涉及NODE 本身之外的其他变量 那么第一种就更合适 。谢谢[脱单doge]

【回复】回复 @图图在南极 :Hi，可以看看后面的 BV14G411P7C1 这期视频，可以加深你对两种递归方式的理解。
爱吃菜花的小成:
向上返回深度的数字是怎么计算的来的呢

【回复】回复 @爱吃菜花的小成 :Hi，是从递归边界出发（空节点处的 0），通过不断加一得到的
好帅一个智障:
这个里面的ans用nolocal声明是不是因为int型变量是传值，对比于第二个视频里的path列表没有声明，是因为列表都是传值是吗

【回复】回复 @好帅一个智障 :如果是用赋值 = 更新，就需要写 nonlocal，调用方法比如 append 是不需要的。