递归

递归是一种应用非常广泛的算法，比如DFS深度优先搜索、前中后序二叉树遍历等等。

递归公式

递归需要满足三个条件：

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

递归的公式可以表示如下：

f(n) = f(n-1) + f(1)，其中f(1) = 1

关键点

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。

注意

递归代码要警惕堆栈溢出、重复计算

改进

递归代码可以改写成迭代循环的非递归代码，可以解决堆栈溢出的问题，通过缓存已经计算过的值，可以解决重复计算的问题。