递归是一种应用非常广泛的算法(或者编程技巧). 也是很多数据结构和算法编码实现的基础. 比如 DFS 深度优先搜索, 前中后序二叉树遍历等等, 所以搞懂递归是学习后面复杂的数据结构和算法的前提条件.
递归在我们的生活中也是很常见的:
在电影院里, 在漆黑的时候, 我们没法直接知道自己是第几排, 于是我们就可以问前一排的人他是第几排, 我们只要在前一个人的基础加一, 但前面一排的人也看不清楚, 所以他也要问他前面的人. 就这样一排一排往前问, 直到问到第一排的人, 因为第一排的人本身就知道自己是第一排, 然后再这样一排一排的把数字传回来. 直到你前面的人告诉你他在哪一排, 于是就知道你自己是第几排了.
上面的例子是一个非常标准的递归求解问题的分解过程, 去的过程叫 "递", 回来的过程叫 "归".
递归问题几乎都可以用递推公式来表示. 上面电影院的例子的是:
f(n)=f(n-1)+1 其中, f(1)=1
f(n)表示你想知道自己在哪一排, f(n-1)表示前面一排所在的排数, f(1)=1 表示第一排的人知道自己在第一排.
根据上面的递推公式, 我们就可以写出递推代码:
- int f(int n) {
- if (n == 1) return 1;
- return f(n-1) + 1;
- }
2. 递归需满足的三个条件
只有同时满足下面三个条件的问题, 才能用递归来解决.
1. 一个问题的解可以分解为几个子问题的解
何为子问题? 子问题就是数据规模更小的问题. 比如前面电影院的例子, 你要知道 "自己在哪一排" 的问题, 可以分解为 "前一排的人在哪一排" 这样的子问题.
2. 这个问题与分解之后的子问题, 除了数据规模不同, 求解思路完全一样
比如电影院的例子, 你求解 "自己在哪一排" 的思路, 和前面一排人求解 "自己在哪一排" 的思路, 是一模一样的.
3. 存在递归终止条件
把问题分解为子问题, 再把子问题分解为子子问题, 一层一层分解下去, 不能存在无限循环, 这就需要有终止条件.
比如电影院的例子, 第一排的人不需要在继续询问任何人, 就知道自己在哪一排, 也就是 f(1)=1, 这就是递归的终止条件.
3. 如何编写递归代码
写递归代码最关键的是 "写出递推公式, 找到终止条件", 然后就是将递推公式转化为代码.
为了理解上面的结论, 我们举例说明:
假如有 n 个台阶, 每次你可以跨 1 个台阶或 2 个台阶, 请问走这 n 个台阶有多少种走法?
如果共有 7 个台阶, 可以是 2 2 2 1, 也可以是 1 2 1 1 2 等等. 走法有多种, 但如何用编程求解总共有多少种走法呢?
可以根据第一步的走法把所有走法分为两类:
第一类: 第一步走了 1 个台阶
第二类: 第一步走了 2 个台阶
所以 n 个台阶的走法就等于先走 1 个台阶后, n-1 个台阶的走法加上先走 2 个台阶后, n-2 个台阶的走法, 所以递推公式就是:
f(n)=f(n-1)+f(n-2)
有了递推公式, 然后就需要找到终止条件.
当只剩一个台阶时, 不需要递推, 因为走法就只有一种, 即 f(1)=1.
当还剩两个台阶时, 这时候可以一步走完(直接跨两个台阶), 或者一步一步的走(每次跨一个台阶), 即 f(2)=2.
当还剩三个台阶时, 可以分解为上面两个子问题, 即 f(3)=f(2)+f(1).
... 以此类推...
所以终止条件就是 f(1)=1,f(2)=2.
结合上面的分析, 就可以得出终止条件和递推公式:
- f(1)=1
- f(2)=2
- f(n)=f(n-1)+f(n-2)
根据上面的公式, 就可以写出如下递归代码:
- int f(int n) {
- if (n == 1) return 1;
- if (n == 2) return 2;
- return f(n-1) + f(n-2);
- }
总结: 写递归代码的关键就是找到如何将大问题分解为小问题的规律, 并且基于此写出递推公式, 然后再推敲终止条件, 最后将递推公式和终止条件翻译成代码.
前面电影院的例子, 递归调用只有一个分支, 即: 一个问题只需要分解为一个子问题. 这种情况, 我们很容易理解, 也能够想清楚 "递" 和 "归" 的每一个步骤, 所以想起来, 理解起来都不难.
但当一个问题要分解为多个子问题的时候, 递归代码就没那么好理解. 例如上面走台阶的例子, 我们几乎不能将整个 "递" 和 "归" 的过程一步一步都想清楚.
其实, 对于递归代码, 我们试图想弄清楚整个 "递" 和 "归" 过程的做法, 实际上是一个进入了思维误区. 很多时候, 我们理解起来很费力, 主要原因是我们自己给自己制造了这种理解障碍.
我们正确的理解方式应该是:
如果一个问题 A 可以分解为若干子问题 B,C,D, 你可以先假设子问题 B,C,D 已经解决, 在此基础上思考如何解决问题 A. 你只需要思考 A 与子问题 B,C,D 两层之间的关系即可, 不需要一层一层往下思考子问题与子子问题, 子子问题与子子子问题之间的关系. 屏蔽掉递归细节, 这样就容易理解很多.
因此, 编写递归代码的关键是, 只要遇到递归, 就把它想象成一个递推公式, 不用想一层层的调用关系, 不要试图用人脑去解递归的每个步骤.
4. 警惕堆栈溢出
在写递归代码时, 容易堆栈溢出, 堆栈溢出会导致系统崩溃, 后果很严重.
递归代码容易造成堆栈溢出的原因
函数调用会使用栈来保存临时变量, 每调用一个函数, 都会将临时变量封装为栈帧压入内存栈, 等函数执行完成返回时, 才出栈. 系统栈或者虚拟机栈空间一般都不大, 如果递归求解的数据规模很大, 调用层次很深, 一直压入栈, 就会有堆栈溢出的风险.
比如前面电影院的例子, 如果我们将系统栈或者 JVM 堆栈大小设置为 1KB, 在求解 f(19999)时便会出现如下堆栈报错:
Exception in thread "main" java.lang.StackOverflowError
递归代码中如何预防堆栈溢出
可以通过在代码中限制递归调用的最大深度来解决堆栈溢出的问题. 一般递归深度超过 1000 后, 就不继续往下递归, 直接返回报错.
例如电影院的例子, 我们可以通过如下改造, 就可以避免堆栈溢出.
- // 全局变量, 表示递归的深度.
- int depth = 0;
- int f(int n) {
- ++depth;
- if (depth> 1000) throw exception;
- if (n == 1) return 1;
- return f(n-1) + 1;
- }
上面写的是伪代码, 为了代码简洁, 有些边界条件没有考虑, 比如 x<=0.
但这种做法并不能完全解决问题, 因为最大允许的递归深度跟当前线程剩余的栈空间大小有关, 事先无法计算. 如果实时计算, 代码就会过于复杂, 会影响代码的可读性. 所以, 如果最大深度比较小, 比如 50,100, 就可以用这种方法, 否则这种方法并不是很实用.
5. 警惕重复计算
在使用递归时, 还会出现重复计算的问题. 上面讲的台阶的例子, 如果我们将整个递归过程分解一下的话, 就如下图所示:
从图中可以看出, 当我们计算 f(5)时, 需要先计算 f(4)和 f(3), 而计算 f(4)时, 还需要计算 f(3), 因此, f(3)就会计算多次, 这就是重复计算问题.
为了避免重复计算, 可以通过一个数据结构 (比如散列表) 来保存已经求解过的 f(k), 当递归调用 f(k)时, 先看下是否已经求解过了. 如果是, 则直接从散列表中取值返回, 不需要重复计算.
按照上面的思想, 可以改进下上面台阶的代码:
- 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 hasSovledList.get(n);
- }
- int ret = f(n-1) + f(n-2);
- hasSovledList.put(n, ret);
- return ret;
- }
在时间效率上, 递归代码里多了很多函数调用, 当这些函数调用的数量较大时, 就会积聚成一个较大的时间成本. 在空间复杂度上, 因为递归调用一次就会在内存栈中保存一次现场数据, 所以在分析递归代码空间复杂度时, 需要额外的考虑这部分开销, 例如上面电影院的例子, 空间复杂度并不是 O(1), 而是 O(n).
6. 将递归代码改为非递归代码
递归代码有利有弊:
利:
代码简洁, 表达能力强
弊:
空间复杂度高, 有堆栈溢出的风险, 存在重复计算, 过多的函数调用会耗时较多.
所以在实际开发过程中, 我们需要根据实际情况来选择是否用递归的方式去实现.
我们也可以将递归代码改为非递归代码, 例如电影院的例子就可修改为如下:
- int f(int n) {
- int ret = 1;
- for (int i = 2; i <= n; ++i) {
- ret = ret + 1;
- }
- return ret;
- }
台阶的例子可修改为如下:
- int f(int n) {
- if (n == 1) return 1;
- if (n == 2) return 2;
- int ret = 0;
- int pre = 2;
- int prepre = 1;
- for (int i = 3; i <= n; ++i) {
- ret = pre + prepre;
- prepre = pre;
- pre = ret;
- }
- return ret;
- }
理论上讲, 所有的递归代码都可以改为这种迭代循环的非递归写法.
7. 内容小结
递归是一种非常高效, 简洁的编码技巧. 只要是满足 "三个条件" 的问题就可以通过递归代码来解决
递归代码比较难写, 难理解. 编写递归代码的关键就是不要把自己绕进去, 正确的姿势是写出递推公式, 找出终止条件, 然后翻译成递归代码.
递归代码虽然简洁高效, 但是也有很多弊端, 例如: 堆栈溢出, 重复计算, 函数调用耗时多, 空间复杂度高等.
递归算法
来源: http://www.bubuko.com/infodetail-3077587.html