数据结构与算法 -- 递归

递归三条件

  1. 一个问题的解可以分解成几个子问题(即数据规模更小的问题)的解
  2. 子问题与原问题,除了数据规模不同,求解思路完全一样
  3. 存在递归终止条件

编写递归代码

  1. 编写递归代码的关键:写出递推公式 + 找到终止条件
  2. 样例:有n个台阶,每次可以跨1个或2个台阶,总共有几种走法?
    • 根据第一步的走法分为两类,第一类第一步走了1个台阶,第二类第一步走了2个台阶
    • 递推公式:$f(n) = f(n-1) + f(n-2)$
    • 终止条件:$f(1) = 1, f(2) = 2$
  3. 对于递归代码,如果试图想弄清楚整个递和归的过程,会陷入一个思维误区
    • 如果问题A可以分解为子问题B、C、D,假设子问题B、C、D已经解决,在此基础上思考如何解决问题A
    • 只需要考虑问题A和子问题B、C、D两层之间的关系即可,无需一层一层往下思考子问题与子子问题的关系
    • 屏蔽递归细节,不要试图去分解递归的每个步骤
1
2
3
4
5
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return f(n-1) + f(n-2);
}

警惕堆栈溢出

  1. 函数调用使用栈来保存临时变量,每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完成返回时才出栈
  2. 系统调用栈或虚拟机栈空间一般都不大,如果递归求解的数据规模很大,调用层次很深,一直压入栈,会有堆栈溢出的风险
  3. 解决方法:限制递归调用的最大深度
    • 但不能完全解决问题,因为最大允许的递归深度与当前线程剩余的栈空间大小有关,事先无法计算
    • 该方法仅适用于最大深度较小的情况

警惕重复计算

为了避免重复计算,可以通过一个数据结构(如散列表)来保存已经求解过的$f(k)$

1
2
3
4
5
6
7
8
9
10
int f(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (solvedMap.containsKey(n)) {
return solvedMap.get(n);
}
int ret = f(n-1) + f(n-2);
solvedMap.put(n, ret);
return ret;
}

递归 / 非递归

  1. 递归有利有弊
    • 利是递归代码的表达力很强,非常简洁
    • 弊是空间复杂度高,有堆栈溢出的风险,存在重复计算、过多的函数调用会耗时较多的问题
  2. 递归代码都可以改成迭代循环的非递归代码
    • 递归本身是借助来实现的,只是使用的栈是系统或虚拟机本身提供的
    • 非递归代码:在内存堆上实现栈,手动模拟出栈和入栈的过程,手动递归本质并没有变,反而增加了实现的复杂度
0%