递归就是这么简单(结论篇)
作者:
| 更新日期:递归,作为一个最基础的知识点,总体回顾一下。
本文首发于公众号:天空的代码世界,微信号:tiankonguse
一、背景
之前写过《递归就是这么简单(原理篇)》,看了原理,发现递归很简单。
但是实际做题做项目的时候,会发现递归很难实现。
这里其实不是递归难,而是我们没有想清楚自己要做什么。
这篇文章简单的总结一下该如何做。
二、递归关系与记忆化
我们知道,递归是一个可以优雅而有效解决很多问题的强大技术。
但是递归不是银弹silver bullet
。
由于时间或空间的限制,并不是所有的问题都可以使用递归解决。
比如有时候递归可能不可预期的问题,如爆栈、死循环等。
When in doubt, write down the recurrence relationship.
有时候,初次看到一个问题的时候,我们并不是马上能想出来怎么用递归解决这个问题。
然而,我们通过梳理问题之间的关系,并用数学式子表达出来后,就会发现可以用递归解决。
这是因为递归的性质和数学式子是很类似的。
通过数学式子,我们可以清晰的看清楚递归关系,并发现问题之间的几何意义。
Whenever possible, apply memoization.
对于某些递归关系,我们很快的实现了对应的代码。
但是有时候,会发现存在重复计算问题,比如斐波纳契数。
此时我们就可以使用记忆化技术,将计算过的结果缓存起来,下次需要的时候直接返回结果。
就这样,我们通过空间换时间的方法,避免重复计算,从而可以大大的降低时间复杂度。
三、合并两个有序链表
题意:给两个有序链表,求合并后的链表。
思路:使用循环的方法也可以做,这里我们使用递归的方法来实现。
递归函数的定义就是题意,即传入两个有序链表,返回合并后的链表头。
当某一个链表为空时,显然可以直接返回另一个链表。
而两个链表都不为空时,链表头肯定是两个链表里面值最小的那个。
所以这里递归就可以找到最小的链表头结点,剩下的递归合并。
最后链表串起来,返回链表头即可。
四、构造二叉搜索树
题意:给1~n
数字,求构造所有合法的二叉搜索树。
思路:咋一看这道题,可能会没有思路。
但是看一下所有的二叉搜索树的根,会发现分别是1~n
,如果我们依次求出所有根的二叉搜索树,合并起来就是所有的二叉搜索树了。
而二叉搜索树有一个性质:左子树的值都小于根,右子树的值都大于根。
这个对应到构造数字上,就是一颗二叉搜索树,其数字区间是连续的。
假设我们要构造[start, end]
这个区间的二叉搜索树,依次枚举根为i
,则左子树区间是[start, i-1]
,右子树区间是[i+1, end]
。
而一个区间构造的子树有多个,左子树和右子树相交,即可得到所有根为i
的二叉搜索树了。
五、爬楼梯
题意:楼梯有n
层,你需要从第1
层往第n
层爬到楼顶。
每次你可以爬一层或者两层,问有多少种不同的方法爬到楼顶。
思路:可以很容易写出一个数学公式来。
大概是f(n) = f(n-1) + f(n-2)
。
而对于n<=1
时,f(n)=1
。
简单的实现递归代码后,发现n
比较大的时候,数据要很久才能跑出来。
这是因为我们重复计算了很多冗余的数据。
如下图
f(10) = f(9) + f(8)
f(9) = f(8) + f(7)
f(8) = f(7) + f(6)
我们计算f(10)
的时候需要计算f(9)
和f(8)
。
而计算f(9)
的时候,又需要计算f(8)
和f(7)
。
计算f(8)
的时候,需要计算f(7)
和f(6)
。
也就是计算f(10)
的时候,我们计算了两次f(8)
和三次f(7)
。
而且这个递归的层数越深,重复计算的次数越多。
这就导致时间复杂度变成指数级别的了。
而我们将计算过的结果保存下来后,每个数字只需要计算一次,复杂度将是O(n)
的了。
六、最后
其实,递归和动态规划是一个东西。
不过两个东西不是一个概念。
递归是一种具体的技术,通过并调用自己,最终计算出结果来。
而动态规划是一种算法思想,通过将问题转化子问题,并用数学公式表达出来。
一般这个数学公式会依赖于自身,所以此时通过递归来解决,就是所谓的push down
,而通过循环递推的解决,则是所谓的push up
。
这里的关键是理解一个问题的转化关系,也就是使用数学公式表达这个问题,剩下的就是代码实现了。
突然发现这个和做项目一样,问题的转化关系,就是项目的架构设计,而架构设计好了,剩下的也是代码实现了。
突然发现,上一篇文章最后提的问题在这里已经得到了解释。
当时提的问题是:
对于递归,已经写过程序的人都会感觉这个很简单。
但是如果看过语法解析或者协议解析的代码,比如json库、protobuf库,就会发现这些库也就是一些递归函数的互相调用。
那为什么说起递归会感觉简单,实现一个json库或者程序语言的语法分析很多人认为很难呢?
你看出这个问题的答案了吗?
-EOF-
本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。