递归的故事（上）

前言

很多搞 iOS 开发的同学都没有学过算法，有一些甚至没有学过数据结构。在很多人的观念中，算法和数据结构只是在面试的时候有用。

这些人的想法对吗？在我看来，也对，也不对。

对于 iOS 开发来说，大多数时候都不需要算法和数据结构知识，但是如果你了解了算法和数据结构知识，在一些关键时候，这些知识会影响你的产品质量和开发效率。

很多人排斥学习这方面的知识，除了用得地方少之外，还有一个原因就是这部分知识比较难。

所以我打算写一个轻松学习数据结构和算法的系列，结合 iOS 开发的故事，让大家看看工作中有哪些地方会接触到数据结构和算法。

这是本系列的第三篇（上），我们讲讲递归。

递归的思维方式

递归是一个非常有意思的思维方式，在自然界，我们遇到一个不会解的问题，都会尽量想办法把这个问题拆解成几个小的问题，然后分而冶之来解决。比如我们高中的时候学立体几何，很多证明就是把立体几何转换成平面几何的问题来求解。

毕业太久不太记得了吧？我举一个例子，比如我们要证明一条直线平行于一个平面，我们就可以转而证明这条直线平行于这个平面上的两条直线。因为经过两条直线，有且只有一个平面，我们就间接证明了这条直线平行于这个平面。

数学还是有点抽象，我们再举一个例子。比如我在学习游泳的时候，教练就会把动作分解，先练习腿部动作，而练习手部动作，然后再整体练习，最后再练习换气。整个教学过程就是把一个复杂的学游泳的事情进行了拆分，分而治之，然后再各个击破之后，就把整个事情搞定了。

但是，递归这个事情却非常反人类的常规思维方式。它是把一个问题的求解过程，转化成若干次相同函数的反复调用过程。因为计算机的计算能力很强，所以能够在大量的反复调用之后，求得最终的解。但是这种做法在真实世界中却无法找到相同的例子，因为对于人类来说，反复调用实在太枯燥和低效了，所以才有了那个著名的笑话：

从前有座山，山里有座庙，庙里有个老和尚和小和尚，老和尚对小和尚在讲故事，他讲的故事是：从前有座山。。。

我想这个笑话，就是递归最好的定义吧。

有关递归的趣事

GNU

递归在计算机界地位很高。Richard Stallman 是美国的自由软件运动精神领袖、GNU 工程的发起者以及自由软件基金会的创立者。作为一个著名的黑客，他的主要作品包括 Emacs 及后来的 GNU Emacs，GNU C 编译器及 GDB 调试器。他所作的 GNU 通用公共许可证是世上最广为采用的自由软件许可证。

你知道他为什么将 GNU 作为他的工程命名和许可证命名吗？他解释说：

GNU’s Not Unix。

在这份解释中，GNU 本身又被使用了，所以就形成了递归。这种计算机界的幽默被著名的 Linus 借鉴，成为 Liunx 的命名原因，因为：

Linux is Not Unix.

如果你感兴趣，维基百科上有一份维护的递归缩写（Recursive Acronym）列表：https://en./wiki/Recursive_acronym

Google

除此之外，Google 也拿递归开过玩笑，有网友晒过一个如下的截图，当你搜「递归」的时候，Google 会问：你搜的是不是递归？然后如果你点的话，又会循环下去，很有意思。

电影

递归从我们程序员的小圈子正式进军好莱坞是在《盗梦空间》电影中。影片《盗梦空间》的剧情结构本身就是一个六层空间嵌套的 “递归” 式叙事。我还记得我和同事看完之后，笑着说：这不就是递归进栈出栈么！

「递归」在《盗梦空间》电影的细节中也被多次呈现，如下是其中一个镜头，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现。

递归的组成

像「老和尚给小和尚讲故事」那种递归一般都不能无限循环下去，因为那样讲的人会受不了，所以一般到了最后，那个人会说：「他讲的故事是：就是这个故事！」。于是，递归结束了。

在计算机编程中，我们在编写递归的时候，同样需要考虑退出条件，否则计算机就会无限计算下去，形成死循环。

所以，对于一个标准的递归程序，应该有两部分组成：

1. 第一部分，也是最重要的部分，退出条件。

2. 第二部分，循环调用自身的代码。

我们来看一个真实的代码，以便更明显的理解上面的话。这是一个求 N 的阶乘的程序。在数学中定义中，N! = N*(N-1)*(N-2)*...1，另外 0 的阶乘是 1，负数没有阶乘。

int fact(int n){ if (n == 0) { return 1; } else { return n * fact(n–1); }}

在这段代码中 if (n == 0) 分支的代码就是退出条件，而 else 部分的代码，就是循环的递归调用代码。

基本上所有的递归程序都有着这样的标准形态，感兴趣的同学可以翻翻链接中的「八皇后问题」的解答，同样是非常标准的递归写法，顺便说一下，这个是 LLVM 的一个性能测试代码。链接见：https:///svn/llvm-project/test-suite/tags/RELEASE_14/SingleSource/Benchmarks/McGill/queens.c

栈的深度问题

递归在实际使用中，还需要考虑栈的深度问题。因为程序在递归时，每一层递归的临时变量和参数，都是被保存在栈中的，所以递归调用的深度过多，就会造成栈空间存储不足。

一般程序的内存区域，除了代码段和数据段外，主要就是分为堆内存和栈内存。下图是一个典型程序的内存布局，我们可以看到，栈是向下生长的，而堆是向上生长的。这句话不太好理解，我打个比方，如果你把内存地址像门牌号编号成 1 ~ 10000，栈的使用就是先用第 10000 号内存块，再用第 9999 号内存块，依次减小编号。而堆的话，是先用第 1 号内存块，再用 第 2 号内存块，依次增加编号。

堆内存通常是没有使用上限的，如果你消耗光了计算机的内存，操作系统还会用硬盘的虚拟内存为你提供更多的内存，而且当前 SSD 作为虚拟内存，读写速度也是不差的。当然，如果你的程序都大量占用了虚拟内存了，很可能也会有内存泄漏问题。这种情况下，多少内存都是不够的，虚拟内存也会被很快消耗光。

但是栈内存空间就不一样了。通常编译器都会指定程序的栈内存空间使用的大小，如果栈内存使用超出了限制，就会触发程序异常退出。这就是著名的栈溢出错误（Stack Over flow）。

著名的程序员问答社区 stackoverflow (http:///) 将此错误作为它的网站域名，也显示出这种错误对于程序员来说是多么地常见。而我们中国程序员圈子里面也给该社区取了一个好玩的名字，叫「爆栈网」，听起来相当霸气。

但是说回 iOS 开发，其实我们真实工作中遇到栈溢出错误的情况并不多，这可能也从一个侧面反映出我们对递归的使用量不大。我查了一下苹果的官方文档（ https://developer.apple.com/library/mac/documentation/Cocoa/Conceptual/Multithreading/CreatingThreads/CreatingThreads.html ），在文档中，苹果对于栈空间大小的默认大小设置如下：

• 对于主线程，栈内存为 1 MB

• 对于非主线程，栈内存为 512 KB

所以说，如果你想「构造」一个栈溢出错误见识一下的话，在 iOS 的 UI 线程中创建一个大小为 100 万的 NSInteger 数组，就肯定会触发「爆栈」了。不过我自己实验了一下，Xcode 报出来的错误是 EXC_BAD_ACCESS ，如下图所示。

尾递归

尾递归的知识涉及函数式编程和编译器优化了。以下是尾递归的 定义：

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。

这个定义有点绕，我们来看看具体的例子，还是刚刚的求 N 的阶乘的例子：

int fact(int n){ if (n == 0) { return 1; } else { return n * fact(n–1); }}

在这个例子中，fact 函数调用自已的位置，在这个函数 return 之前，但是返回值没有被直接使用（在返回前，它乘以了n），所以这个fact 函数不是一个尾递归的函数。

我们再看一个用 Swift 写出来的尾递归的例子：

func sum(n: Int, acc: Int) -> Int { if n == 0 { return acc } else { return sum(n - 1, acc + n) }}

在这个例子中，sum 函数就是一个尾递归函数。

刚刚讲了很久递归太深对于栈空间的影响，但是尾递归的函数的特点，使得它可以不消耗栈空间来完成递归函数的计算。但是这个特性需要编辑器做特殊的优化。具体编译器优化的过程我就不讲了，因为很复杂，我也没有弄得特别清楚。

那么问题来了？苹果最新的 Swift 语言引入了大量的函数式编程特性，它的编译器是否支持尾递归优化呢？带着疑问我查了一下，很可惜，当前网上的 实验 和 文档 都表明 Swift 暂时还不支持尾递归优化。

在下一部分中，我们将讨论两个具体 iOS 开发中应用递归的案例。