数据结构与算法-递归

Posted on | Edited on | In ,

什么样的问题可以用递归解决

  1. 可以将一个问题分解成若干子问题
  2. 主要问题和子问题之间的处理过程是一样的。
  3. 存在递归终止条件

如何写一个递归程序

  1. 分解问题，推导出递推公式
  2. 找到程序的出口，即递归结果

递归程序的注意事项

  1. 防止堆栈溢出–增加深度的参数
  2. 防止重复计算–增加散列表等方式记录计算结果如果有计算结果直接返回

例子：斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private Map<Integer, Long> map = new HashMap<>();

/**
 * 递推公式f(n)=f(n-1)+f(n-2)，结果：n==1 return 1 n==2 return 1
 * @param n
 * @return
 */
public long cal(int n) {
    //递归结果
    if (n == 1 || n == 2) {
        return 1;
    }

    //记录结果避免重复计算,如果没有这个会特别的满
    if (map.containsKey(n)) {
        return map.get(n);
    }

    //计算
    long ret = cal(n - 1) + cal(n - 2);
    map.put(n, ret);
    return ret;
}