关于递归的理解以及是否应该使用递归

Question

以二分搜索树增加元素为例

1、递进归出

递归拥有两个阶段分别是递进阶段 归出阶段也就是相当于出入栈。
1、递进阶段
在这个阶段和循环相同，那就是只是循环找到最后的终止条件，这个阶段的代码位置在函数体调用自身之前,在这个阶段也可以进行一些操作，比如修改元素，以及其他一些不对二分搜索树连续性产生破坏的操作。
2、归出阶段
这个阶段相当于再把之前的循环反向执行一边，这个阶段的代码位置在函数体调用自身之后，在这个阶段可以进行一些破坏二分搜索树连续性的操作，同时也可以把递进阶段的操作放到归处阶段。

2、二分搜索树分析

我把二分搜索树看成两层循环，第一层事ROOT节点本身，第二层是ROOT的左右节点。
根据老师说的首先要确定循环的终止条件。

2.1、关于循环的终止条件

函数传入的Node节点为空的话就是终止条件，同时函数语义是增加元素，我们要在终止条件里创建一个Node节点并返回。

2.2、关于循环调用本身

根据用更小问题的解构建原问题的答案原则，因为终止条件会返回给我们一个新的节点，那么我们的到了这个节点。需要根据这个节点构成原问题的答案，如何构成那就是把这个解挂载到当前节点上。
但是在这里我们遇到了一个问题，如何确认返回的节点是左节点还是右节点？
这个时候我们就需要在函数调用前增加判断。

何时使用递归

老师递归我大概能弄懂了，但是究竟什么时候要使用递归我现在很纠结，老师有没有什么这方面的建议。
还有我递归的理解是否有问题。

Answer 1

liuyubobobo 2019-08-27 06:52:49

什么时候可以使用递归求解问题，什么样的问题可以使用递归求解？这个问题恰恰是递归难的地方，也是算法难的地方。因为，不是那么简单的，拿到一个问题，我们就可以简单地一个性质一个性质对，然后就能确定，这个问题可以使用递归求解了。

如果一定要总结，那么就是，这个问题具有递归性质。

所谓的递归性质，就是，为了解决原问题，我们可以先解决比原问题的规模要小的同等问题，之后组合这些更小规模问题的解，获得原问题的解。

比如二分搜索树的元素添加。我们想在以node为根节点的二分搜索树中添加一个元素，可以在以node->left为根节点的二分搜索树中添加元素；或者在以node->right为根节点的二分搜索树中添加元素。如果添加好了，我们自然就完成了在以node为根节点的二分搜索树中添加一个元素的任务。（在以node->left为根节点的二分搜索树中添加元素；或者在以node->right为根节点的二分搜索树中添加元素，就是规模更小的同等问题）

比如归并排序，我们可以对数组左半部分做归并排序，对数组右半部分做归并排序，之后，两部分合起来，整个数组就排好序了。（对数组左半部分做归并排序，对数组右半部分做归并排序，就是规模更小的同等问题）

比如链表反转，翻转以 head 为头结点的链表，我们可以先翻转以 head->next 为头结点的链表，之后，将饭庄结果的尾结点链接上 head，就完成了翻转以head 为头结点的链表。（翻转以 head->next 为头结点的链表，就是规模更小的同等问题）

但是，你现在了解什么情况下可以使用递归了吗？大概率的没有。因为一个问题是否有递归性质，怎么定义其中的递归性质，我不认为有一定之规。上面的三个例子，又什么共同点？我还可以说更多可以使用递归解决的问题：斐波那切数列；快速幂算法；辗转相除求最大公约数；棋盘覆盖；走迷宫；汉诺塔.....

反正我的水平不足以说明白，怎么就能一定使用递归求解问题了。我认为这些问题没有规律。实际上，我不认为这个世界上存在什么黄金准则，一比照，就能知道，这个问题可以使用递归求解。否则，递归就太简单了，算法也太简单了。

怎么办？我认为只能多见问题，见多了，就有经验了，面对问题，就能自然而然地看出其中的递归性质。可以参考我的公号文章《高效学习的秘密》第8条：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247483836&idx=1&sn=90854aa76507281403e4dd9cd434a12b&chksm=fd8caefacafb27ec78f999fde4f1217c04c6e2ff28cf51fe511d8fa29d484d9281ff91de8c9c&token=252344042&lang=zh_CN#rd 

我经常说，dp 问题，要想熟练掌握，100 道刚起步。实际上，深入理解 dp 问题，是建立在深入理解递归的基础上的。计算机专业的同学，见的写的递归函数，更应该是数以百计的。在算法领域，递归简直无处不在。

在这门课程中，从这章开始，近乎每一章的代码都和递归有关。

在我的《玩转算法面试》课程中（https://coding.imooc.com/class/82.html），从第七章开始，每一章都和递归有关。

如果你去看 Leetcode 上的问题，和 Tree，DFS，动态规划 相关的所有问题，都和递归有关。

不要着急，多去看。见多了，你对递归的理解，自然就会越来越深刻，对什么样的问题应该怎么使用递归去解决，也自然会越来越有感觉。

加油！：）