public int f(int n) {
  if (n == 1) return 1;
  if (n == 2) return 2;
  
  // key是n，value是f(n)。将重复结果缓存起来，避免重复递归
  if (hasSolvedList.containsKey(n)) {
    return hasSovledList.get(n);
  }
  
  int ret = f(n-1) + f(n-2);
  hasSovledList.put(n, ret);
  return ret;
}

(3)递归死循环“环”问题

        例如： 用户A推荐用户B来注册，用户B又推荐了用户C来注册。我们可以说，用户C的“最终推荐人”为用户A，用户B的“最终推荐人”也为用户A，而用户A没有“最终推荐人”。

        在数据库表中，我们可以记录两行数据，其中actor_id表示用户id，referrer_id表示推荐人id。因此， 给定一个用户ID，如何查找这个用户的“最终推荐人”？

    可能产生的问题：

• 递归深（见上解决办法）

• 如果数据库里存在脏数据，我们还需要处理由此产生的无限递归问题。比如demo环境下数据库中，测试工程师为了方便测试，会人为地插入一些数据，就会出现脏数据。如果A的推荐人是B，B的推荐人是C，C的推荐人是A，这样就会发生死循环，即 A-B-C-A“环”。

//原始代码
long findRootReferrerId(long actorId) {
  Long referrerId = select referrer_id from [table] where actor_id = actorId;
  if (referrerId == null) return actorId;
  return findRootReferrerId(referrerId);
}

//改进代码，缺点是内存占用量变大了（会最少）
long findRootReferrerId(long actorId, Set hasSolvedSet) {
  Long referrerId = select referrer_id from [table] where actor_id = actorId;
  if (referrerId == null) return actorId;
  if(hasSolvedSet.contains(referrId)) return ;  //如果已经处理过了则退出
  return findRootReferrerId(referrerId, hasSolvedSet.add(referredId));
}

【补充：内存栈帧和栈深度区别】

//如果栈帧中占用内存较大，那么栈的最大深度也会降低

//Exception in thread "main" java.lang.StackOverflowError

int f(int n) {

    ArrayList<Integer>list =new ArrayList<>();

    list.add(1);

    if (n == 1) return 1;

    return f(n-1) + 1;

}

main(String[] args) {

    f(10000);

}

//正常执行不报错

//原因分析:JVM默认单个线程栈的大小为512k。 当设置-Xss变大后，上面代码就可以执行了。由此可知，递归运算能否正常执行由

  栈帧+栈深度共同决定

int f(int n) {

        if (n == 1) return 1;

        return f(n-1) + 1;

    }

main(String[] args) {

    f(10000);

}