1回答

liuyubobobo

2019-08-27

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

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

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

比如二分搜索树的元素添加。我们想在以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，动态规划 相关的所有问题，都和递归有关。

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

加油！：）

3

0