数据结构与算法之美-递归

数据结构与算法之美-递归

递归作为一种应用非常广泛的算法(或者编程技巧),在很多数据结构和算法的编码实现都会用到递归。例如DFS深度优先搜索、前中后序二叉树遍历等等。

什么情况下可以使用递归?

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

如何编写递归代码?

首先分析问题,确定该问题是否可用递归求解。若可用,则最关键的部分就是写出递推公式了。下面分析一个常见的爬楼梯问题:假如有n个台阶,每次你只能跨1个台阶或两个台阶,问走完这n个台阶,你有多少中走法。

仔细思考后,实际上可以根据第一步的走法把所有的走法分为两类,第一类是第一步走一个台阶,第二类就是第一步走两个台阶。那么第一类的情况下的走法就等于走完一个台阶后剩下的n-1个台阶的走法了,同理,第二类的情况就和走剩下的n-2个台阶的走法一样了。总结起来n个台阶的走法就等于n-1个台阶的走法(第一类)加上n-2个台阶走法(第二类),写出递推公式:f(n) = f(n-1) + f(n-2)。

有了递推公式,递推代码基本就完成了一半了。接下来就是找递推终止条件了,当n=1时只有[{1}]这一种走法,当n=2时有[{1,1},{2}]两种走法。所以递推终止条件就是f(1)=1,f(2)=2。这个时候可以拿n=3,n=4来验证一下。将递推公式和终止条件放在一起就是:f(n) = f(n-1) + f(n-2) 其中f(1)=1,f(2)=2。这不就是斐波那契数列吗,点击查看具体的递归代码。

写递归代码需要注意的问题

警惕堆栈溢出

我们知道函数调用会使用栈来保存临时变量。每调用一个函数,都会将临时变量封装为栈帧压入内存栈,等函数执行完时返回时才出栈。系统栈或虚拟机栈空间一般都不大,如果递归深度很深,就会有堆栈溢出的风险。针对这种情况,我们可以通过设置最大深度限制值来解决这个问题。当递归深度超过限制值(比如1000)之后,我们就不继续往下递归了,直接返回失败。

警惕重复计算

递归调用过程中经常会出现重复计算某一f(k)的值,为了避免重复计算,我们可以通过一种数据结构(例如散列表)来保存已经求解过的f(k)。

空间复杂度较高

递归调用每进行一次就会在内存栈中保存一次现场数据,所以通常的递归算法的空间复杂度为O(n)。