『数据结构与算法』—— 递归

  |     |   本文总阅读量:

定义

最简单的例子,常见的推荐有奖营销活动,如果需要找到最终的推荐人,那么就需要用到 递归。递归是一种应用非常广泛的算法或者是编程技巧。其中有两个难点:动态规划和递归。

递归需要满足的三个条件

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

编写递归代码

编写递归代码关键在于 写出递推公式,找到终止条件。一个简单的例子:

假如这里有 n 个台阶,每次可以跨 1 个台阶或者 2 个台阶,请问走 n 个台阶有多少种走法?

仔细想一下,所有的走法可以分成两类,第一类是第一步走了 1 个台阶,另一类是第一步走了 2 个台阶。所以 n 个台阶的走法就等于先走 1 个台阶后,n-1 个台阶的走法加上先走 2 个台阶后,n-2 个台阶的走法,用公式表示就是:

$f(n) = f(n-1)+f(n-2)​$

当递推公式出来后,递归代码基本上就走了一半。终止条件和递推公式合并后就是:

1
2
3
f(1) = 1;
f(2) = 2;
f(n) = f(n-1) + f(n-2);

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

还有一点:编写递归代码的关键是,知道遇到递归,我们就把它抽象成一个递推公司,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。

注意点

警惕堆栈溢出

递归代码需要重复调用自身的方法,当调用次数过大是,很有可能就会抛出堆栈溢出的异常。函数调用会使用栈来保存临时变量,每调用一个函数,都会临时变量封装为栈帧压入内存栈,等函数执行完成返回后,才会出栈。系统栈或者虚拟机控件一般都不大。如果递归求解的数据规模很大,调用层次很深,一直压入栈,就会有堆栈溢出的风险。

如何避免堆栈溢出的出现,最常见的办法就是使用循环遍历来替代递归,但是可读性可能会降低。后面会介绍例子。

警惕重复计算

如果把算台阶走法的题目分解一下,就是这样的:

从图中可以发现有些是重复计算的,为了避免计算,就可以通过 HashMap 来保存计算的值,优化这个问题。

实战

首先使用普通的递归方式来实现台阶走法那个题目:

1
2
3
4
5
private int findLadder(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return findLadder(n - 1) + findLadder(n - 2);
}

转换成循环迭代的方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
private int findLadderNormal(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
int result = 0;
int pre1 = 1;
int pre2 =2;
for (int i = 3; i <= n; i++) {
result = pre1 + pre2;
pre1 = pre2;
pre2 = result;
}
return result;
}

在递归的基础上,优化重复计算:

1
2
3
4
5
6
7
8
9
10
private int findLadderAdvanced(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (cached.containsKey(n)) {
return cached.get(n);
}
int result = findLadderAdvanced(n - 1) + findLadderAdvanced(n - 2);
cached.put(n, result);
return result;
}

总结

递归是一种非常高效、简洁的编码技巧。只要满足三个条件的问题就可以通过递归代码来解决。

不过递归代码也比较难写、难理解。编写递归代码的关键就是不要把自己绕进去,正确姿势是写出递推公式,找出终止条件,然后再翻译成递归代码。

参考自极客时间


赏我 e(=2.72) 元咖啡钱吧,您的支持将鼓励我继续创作!



文章目录
  1. 1. 定义
    1. 1.1. 递归需要满足的三个条件
  2. 2. 编写递归代码
  3. 3. 注意点
    1. 3.1. 警惕堆栈溢出
    2. 3.2. 警惕重复计算
  4. 4. 实战
  5. 5. 总结
您是第 位小伙伴 | 本站总访问量 | 已经写了 105.0k 字啦

载入天数...载入时分秒...