递归算法

什么是递归？

递归就是在过程或函数里调用自身。

先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决， 子问题再拆解成子子问题，...，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,....,直到最开始的问题解决

递归需要满足三个条件

1. 一个问题的解可以分为几个子问题的解
2. 这个问题与分解后的子问题，除了数据规模不同，求解方式相同
3. 存在递归终止条件

实现思路：

1. 定义函数
2. 找出递推公式
3. 将递推公式带入函数中
4. 检查时间复杂度是否可行

递归题

1. 电影院
2. 求阶乘
3. 斐波那契数/求台阶走法数/矩形覆盖
4. 数字反转
5. 汉诺塔

递归注意点

1. 重复计算
2. 栈溢出

一文看懂什么递归（算法小结） (opens new window) 干货｜五个递归题总结 (opens new window)