递归算法
什么是递归？
递归，在计算机科学中是指一种通过重复把问题分解为同类的子问题而解决问题的方法，通俗来讲，递归表现为函数调用函数本身。在知乎上有一个比喻递归非常形象的例子。 “递归最恰当的比喻，就是查词典。我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。”. ### 递归的特点 事实上，递归有两个显著的特征，终止条件和自身调用： * 自身调用：原问题可以分解为子问题，子问题和原问题的求解方法是一致的，都是调用自身的同一个函数 * 终止条件：递归必须有一个终止的条件，即不能无线循环的调用自己
递归与栈的关系
递归的过程也可以理解为出入栈的过程 比如说我们利用递归计算3的阶乘，因为3>1,所以进入下一个递归，2>1，再进入下一个递归，1=1，开始计算，依序返回，在这里，我们可以发现先进去的3反而是最后执行的，这就类似于栈的性质
递归的经典应用场景
- 阶乘问题
- 二叉树深度
- 汉诺塔问题
- 斐波那契数列
- 快速排序，归并排序（分治算法中体现递归）
- 遍历文件，解析xml文件
递归解题思路
- 定义函数功能
- 寻找递归终止条件
- 递推函数的等价关系式
递归存在的问题
- 递归调用层级太多，导致栈溢出问题
- 递归重复计算，导致效率低下
栈溢出问题：
- 每一次函数调用在内存栈中分配空间，然而每个进程的栈容量是有限的
- 当递归调用的层级太多时就会，就会超出栈的容量，从而导致调用栈溢出
- 其实，我们在前面小节也讨论了。递归过程类似于出栈入栈，如果递归次数过多，栈的深度就需要越深，最后栈容量就不够了
重复计算导致效率低下
递归处理时，有些问题如果不加以处理，会造成多次重复计算，降低程序的运行效率
参考：https://mp.weixin.qq.com/s/tqGKHZzSyDBgEp-oWsOztQ