漫话递归与迭代

源起

今天无意中看到这句话：

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 

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

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

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

工程

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

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

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

人生

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

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

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

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

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

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

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

参考文献：

• 知乎文章递归算法，周闖

• Difference between Recursion and Iteration
  

• CMMI DEV 1.3