写点什么

漫话递归与迭代

用户头像
Justin
关注
发布于: 2021 年 02 月 03 日
漫话递归与迭代

源起


今天无意中看到这句话:


To iterate is human, to recurse, divine.

—— L. Peter Deutsch


我在网上找了几个翻译,觉得这个不错:迭代者为人,递归者为神


这句话很玄妙,仔细想一下,其实我没搞懂 Deutsch 先生到底是在鼓励我们多用迭代,还是多用递归。神乎其技自然是极高明的做法,但也怕是此曲只应天上有,我等凡人最好还是老老实实用迭代?


顺便说一下,说这句话的 L. Peter Deutsch,虽然他姓德意志(Deutsch),但其实是美国人。他是 Ghostscript 的作者。做科研的同学们用 Latex 写论文,生成 PDF 或者 Postscript 文件,没这个 30 年前开发的软件不行。


编程


递归和迭代,都是计算机科学中写代码解决问题的方法,先从编程的角度来看。不精确的说,当程序调用自身,就是递归;有循环,就是迭代。


def factorial_recursive(n): 	if (n == 0): 		return 1
return n * factorial_recursive(n - 1)
def factorial_iterative(n): result = 1
for i in range(2, n + 1): result *= i
return result
复制代码


一般来说,递归和迭代的选择,是时间复杂度和代码长短之间的权衡。


很多情况下,使用递归算法,代码会简洁易懂。递归算法本身是一种解决复杂问题的有效思路,递归带有「层层递进,终得回归」的意思。就是说,通过把复杂问题转化为结构上类似,但更容易有出路的子问题,再对子问题做同样的转化,直到问题足够简单,可以直接有答案,也就是找到了递归出口。进而逐层回归,得到原始问题的答案。


果时间复杂度是重点,而且递归调用的层次很多,就最好用迭代,否则就会带来极高的时间复杂度。甚至,在递归退出条件指定错误的情况下,可能会发生无限递归调用,最终导致系统崩溃。迭代算法代码往往更长,通常也更难编写,因为你需要更全面的理解问题。而不是像递归那样,只需要找到问题结构和退出条件就可以了。但迭代的好处是时间复杂度更可预测。如果你是游戏开发者,我劝你尽量用递归,而不是迭代。


工程


在工程领域,递归和迭代有着相似的含义。


当一个过程应用于系统结构中系统元素的连续层次时,就会发生递归。一个应用的结果作为系统结构中下一级的输入。例如,测试过程就可以针对整个系统、某个子系统、某个服务、甚至某段核心代码进行,具体要深入到什么程度,取决于最终产品的大小和复杂度。


迭代发生在同一系统级重复的过程中。一个过程的实施会产生新的信息,将这些信息反馈到下次迭代的过程中。例如,在需求和技术方案之间很可能会出现迭代,通过在需求和方案之间反复迭代,可以确保需求和方案很好地对齐,并且各自优化到更高水平。


人生


人的成长,也会面临递归和迭代的选择。


人生对于我们每一个人来说,都是复杂而未知的。我们对人生的认识,都是在不断学习、思考、实践当中,不断深化。而对人生的认识深化之后的我们,才有可能在新的层次上,给自己设定更高的目标,运用上个层次增长的见识、技能、智慧,开启新的冒险。


和递归一样,我们对问题的认知,解决问题的能力,是可以在时间维度上形成积累的


虽然我们面临的问题,在每个人生阶段都不尽相同,但却有类似的结构。小时候做一道数学题的心路历程,和长大后学会构建一个系统,从某种意义上,没有本质的不同。


对于人生这样一个充满未知的命题,几乎不可能事先安排好一切,按部就班做迭代。很多时候,我们一直在做重复性工作,甚至选择所谓更单纯的工作,看似迭代,但其实是放弃了自我的成长。现实世界是复杂的,并不会因为我们选择不看它复杂的一面,而变得简单。这样的迭代,是没有意义的。


从古代修筑巴比伦塔开始,人类就是在不断挑战人神的边界。神之递归,期待成长的你值得拥有。


今日立春。立,开始;春,成长。祝愿大家在新的轮回里,以递归的方式成长。


参考文献:



发布于: 2021 年 02 月 03 日阅读数: 88
用户头像

Justin

关注

对世界好奇,对自己好奇 2018.04.14 加入

TGO 北京会员,乐城堡联合创始人

评论

发布
暂无评论
漫话递归与迭代