算法基础：递归

学习提示

• 初学的朋友会觉得「递归」很难，这是很正常的，一开始先模仿，不理解的话先放一放，以后接触的问题多了，就慢慢理解了。学习「递归」是一个循序渐进的过程，需要一定量的练习；
• 「递归」并不是一个孤立的概念，「递归」贯穿了整个算法与数据结构学习的始终，在以后还有很多机会接触和学习「递归」，没有必要一开始就要求自己深刻理解「递归」；
• 与「递归」相关的话题有：「分治算法」（请见「归并排序」）「深度优先遍历」「回溯算法」「栈」「动态规划（记忆化递归）」，可以在学习这些算法或者数据结构的过程中慢慢理解「递归」。

使用「递归」解决问题的思想：自顶向下

• 「递归」体现的是一种「自顶向下」（自上而下）解决问题的编程思想，「递归」是编程中特有的一种语法现象；
• 使用「递归」解决问题，有「拆分问题」与「组合问题的解」两个部分。

「递归」与「遍历」

• 如果一个问题需要「遍历」，很多时候也可以使用「递归」实现；
• 特别地，在 树形问题 或者图的问题中执行「深度优先遍历」，在代码层面上，我们看到的就是「递归（自己调用自己）」。

文字教程

• LeetBook 之「递归」专题：第 1 节 递归与分治 (opens new window)
• LeetBook 之「递归」专题：第 2 节 递归函数的设计思想：分而治之（减而治之） (opens new window)

说明：视频教程和文字教程中已经介绍得很详细了，因此本节不再过多讲述。

总结

• 「递归」是一种先「自上而下」，再「自下而上」的求解问题的过程；
• 「递归」体现的算法思想是「分而治之」；
• 「递归」（「分治算法」）的两个过程：「拆分问题」与「组合子问题」的解；
• 「递归」的执行流程：深度优先遍历；
• 支持「递归」的数据结构是「栈」。

---

作者：liweiwei1419 链接：https://suanfa8.com/recursion 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。