递归
定义
递归是一种算法，指程序不断调用自己的过程。
同时，递归亦是一种思考问题、描述问题的方法。基本思想是把一个复杂的或者大规模的问题转化为一系列简单的、小规模的问题的重复。
特点
- 所有的递归程序，都可以写成非递归的形式。在非递归的版本中，需要程序员手动维护一个栈，来模拟原来程序的调用栈的使用。
- 使用递归解决的问题，往往都可以先通过数学归纳法对本问题进行归纳（比如斐波那契数）。先思考，再尝试归纳，再写程序，是一个比较好的思路去写程序。
如何设计递归程序
设计出一个好的递归程序，需要明确以下三个要素
要素一：明确函数任务 明确你这个函数是用来完成什么任务的
要素二：明确递归结束条件 所有递归的程序必须设置清晰的递归结束条件，并设置正确的返回值。一般在结束的递归其返回值常为一个固定值。
要素三：明确分解问题的思路（即找出函数的等价关系式） 简单来说，就是找到 和 的关系，找到问题重复的逻辑，这一步可以采用数学归纳法。我们要明确如何将问题的规模变小。
递归中的Trick
递归中有时会经常涉及到重复计算，造成性能的下降和算力损失。
比如下图中，我们采用递归的时候，就会重复计算相同颜色的块。
对于上述问题，我们的解决思路是善用记忆或者缓存 （memoization）
对于一个递归程序中的中间结果，我们可以将这些中间结果存储在缓存中，每次递归前在缓存中找一下看看是不是已经计算过了，缓存可以使用哈希表来存储。
什么问题适合递归
- 可以用数学归纳法归纳出一般规律的
- 问题规模和问题的解决方法没有关系，无论多大规模的问题，都可以分解成若干个小规模的子问题，并且其解决方法都是一样的。
递归有害
递归的程序很难估计递归的深度，有可能造成调用栈溢出。因此实际生产中往往不会采用递归，而是改写成非递归的形式，并且手动控制调用栈的深度在合理的深度。
然而，递归代码更少，看上去更牛逼。
和分治的区别
参见 递归-区别-分治
如何计算递归行为的时间复杂度
使用 Master 公式