满足递归的三个条件
- 一个问题的解可以分解为几个子问题的解
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
- 存在终止条件
如何编写递归代码
- 重中之重：找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。至需要理解第一层主问题和第二层子问题的关系即可，不用把递归的每一个步骤都理解
eg: 走台阶问题：有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？f(n) = f(n-1)+f(n-2)
- 警惕==栈==溢出
- 利用散列表避免重复计算