递归作为一种应用非常广泛的算法(或者编程技巧),在很多数据结构和算法的编码实现都会用到递归。例如DFS深度优先搜索、前中后序二叉树遍历等等。
什么情况下可以使用递归?
- 一个问题的解可以分解为若干个子问题的解。
- 这个问题与分解之后的子问题,除了数据规模不同,求解思路完全一样。
- 存在递归终止条件。
如何编写递归代码?
首先分析问题,确定该问题是否可用递归求解。若可用,则最关键的部分就是写出递推公式了。下面分析一个常见的爬楼梯问题:假如有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)。