递归

使用递归的条件

1. 可分解
2. 母子问题思路完全相同
3. 有终止条件

编写思路

如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了。

借助 map 解决多次计算问题

public int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  // hasSolvedList可以理解成一个Map，key是n，value是f(n)
  if (hasSolvedList.containsKey(n)) {
    return hasSolvedList.get(n);
  }
  int ret = f(n-1) + f(n-2);        //这里将 f(n-1) 当成已知值去思考
  hasSolvedList.put(n, ret);
  return ret;
}