Hueihuea / 关于递归是否都能写成循环及其性能问题的回答

本文是对知乎上“所有递归都可以改写成循环吗？”问题的回答

话说递归层次比较深的话容易造成stack overflow,还被认为效率不高，而且有人表示所有的递归都可以改写成循环，这是真的吗？

林锐博士的书中曾表示：所有的递归都可以改写成循环，而且认为递归的效率不高。 而王垠博士则认为递归比循环强。 “递归的数据总是需要递归的程序来处理。虽然递归有时候表现为另外的形式，比如循环(loop)，但是“递归”这个概念比“循环”更广泛一些。有很多递归程序不能用循环来表达” http://blog.sina.com.cn/s/blog_5d90e82f01018ge9.html

“而其实递归比循环表达能力强很多，而且效率几乎一样。有些程序比如解释器，不用递归的话基本没法完成。” http://blog.sina.com.cn/s/blog_5d90e82f01015271.html

王垠写解释器可是很在行的啊，对循环，递归的理解也应该不错吧。

在此请教各位啦

我们不管林锐和王垠到底如何，就说标题问题本身（不得不说这是个老生常谈到没必要再谈的话题，但他就神奇在总是让你想谈谈，可能是因为他比较具有迷惑性吧）。

所有递归都可以写成循环

国内外学界和业界主流观点：所有递归都可以写成循环。

你可以在《编译原理》里找到“一切递归代码都可以写成栈+循环的形式”

但是递归和循环这个词不太严谨，有歧义。

在一般编程语境下：

递归是指函数自己调用自己

循环是指一段能重复执行零或多次的代码，具体表现成for等控制流语句

很明显，递归和循环是等价的，互相能写成对方的形式。

在递归论语境下：

递归是有明确定义的，但是循环没有，有的朋友认为循环是尾递归。

那么问题就变成了：递归都能改写成尾递归。

由于尾递归是递归的真子集，“递归都能改写成尾递归”显然是不成立的。

这就是为什么有的朋友认为“并非所有递归都能写成循环”。

如果从可计算性理论的“邱奇-图灵论题”出发：

递归函数和图灵机（无限内存和循环能力）在计算能力上等价。

亦或者从迪杰斯特拉等人的结构化程序设计理论出发：

程序的基本控制流是顺序 选择 循环。

他们证明了拥有这三种控制流的编程语言是图灵完备的（默认无限内存能力）。

需要解释一下 之所以是循环不是goto 是因为他们搞结构化程序设计就是为了反对当时goto的滥用。

还有朋友提到CPS变换，CPS变换确实可以把递归都改写成尾递归的形式，这样支持尾递归优化的编程语言可以对其进行机械性的优化，但是，就算使用CPS变换，需要的空间复杂度是不会改变的，依旧要存储前面未完成的计算来完成递归中回归的过程，不过是把一般递归形式改成了闭包尾递归罢了。当然这在工程上有一定意义，把栈空间的压力转移到了堆空间上。

但我觉得这俩种语境都不太好，因为一般编程语境不够学术和严谨，但递归论，或者说计算理论，在中国不属于计算机专业的必修课，很多人可能都不知道里面的很多概念，不够普适。而且递归论的语境里循环的概念是不明确的，容易引起不必要的纠纷。

我觉得不如用《Structure and Interpretation of Computer Programs》中的俩个简单的概念来回答这个问题：

递归计算过程：递归计算过程是一种其执行需要解释器维护一个随时间增长和收缩的调用栈的过程。该调用栈用于跟踪在后续计算中必须执行的延迟操作链。这个过程消耗的存储空间与步骤数成正比。

迭代计算过程：迭代计算过程是一种其状态可以由固定数量的状态变量完全描述的计算过程。在过程演进时，存在一套固定的规则，用于在状态转换时更新这些变量，以及一个（可选的）结束测试来指定终止条件。这种过程可以在恒定大小的存储空间内执行，其空间消耗与计算步骤数无关。

那么我们知道，一个不依靠显式栈或者其他无限内存能力的可重复代码（循环）的计算过程，是迭代计算过程，递归和依靠显式栈或者其他无限内存能力的可重复代码（循环）的计算过程，是递归计算过程。显而易见的，一切递归计算过程不能写成迭代计算过程，反之亦然。

注意：递归计算过程要求你的计算过程中，变量必须随时间改变，不可以一直不变。而迭代计算过程要求你的变量必须一直不变，不能多也不能少，不能声明9个变量但某次计算只有8个变量有意义。（注意，这里的变量并非编程语义中的变量，而是状态变量，迭代计算过程的状态变量必须数目一定且全部有意义，保证了依靠巨大状态空间伪装成迭代计算过程的递归计算过程依旧是递归计算过程，举个例子，我申请了一个arr[10000000]来用循环模拟递归，这个计算过程依旧是递归计算过程，因为在计算过程的状态空间中存在无意义的状态变量；亦或者，反过来，用递归函数去描述迭代计算过程，这个过程中额外的调用栈信息对你的计算过程是没有意义的，也就是实际状态变量是不变的，尽管是递归形式，他也依旧是迭代计算过程）

关于性能问题：循环通常优于递归

由于递归和循环的计算能力的等价的，理论上讲他们的最优实现的复杂度也是一样的。

但是，现实编程里就不一定了。

现实里由于硬件特性，递归需要额外维护额外的栈帧信息，且栈帧的内存连续性不良，同时对寄存器、高速缓存和分支预测不友好，导致递归最优性能通常比循环弱。这是国内外学界和业界的主流观点，你在《Algorithms + Data Structures = Programs》等书中都能找到这样的观点。

在有的语言中，调用函数的额外开销比较大，比如Java（栈帧信息更丰富，安全检查更多），这个情况下显式栈+循环对递归的性能优势通常表现的很明显。

插入一个笑话：JVM标准不要求尾递归优化，所以很多JVM遇到尾递归一样会爆栈。

但是，如果是在调用函数额外开销极小的语言中，比如CPP，那么在都使用“软件方法”维护栈（递归维护调用栈，循环维护显式栈），在一定递归深度内，递归和循环的性能应该是相当接近的。 但如果要考虑内存连续性和缓存命中率等问题，那就如我们刚刚说的那样，由于硬件特性，递归天生劣于循环。

可是，有一个问题，在x86等框架下，指令集是包含push等调用栈指令的，这个时候编译器默认生成的“调用硬件维护调用栈的方案”，在递归深度很小的情况下就很有可能比你手写的“软件维护显式栈的方案”快的多。这就是递归比循环快的特例，这种特例其实相当少见，而且，这也是考虑内存连续性和缓存命中率等问题的。

（当然，需要指出的是，手写的循环代码本身也运行在系统调用栈之上，但这部分栈帧开销是两者共有的，并非我们在此比较的重点。）

不过也有几种极端的理想情况：

硬件性能无限，任何算法都立即完成，那这没有任何讨论的必要，硬件牛逼就完了。

编译器的优化能力无限，递归和循环编译出的机器码完全一致。

机器有无限的学习能力，能自动优化内存中的程序，运行一段时间后递归和循环的机器码完全一致，从此在后续计算中性能一致。

不过这几种情况都属于想一想就行，不要想太多，哈哈。

不过说到底，递归和循环之所以在性能上有差距，不就是因为他们天生的底层行为有差异吗？不如直接写汇编，递归函数和循环语句都不存在了，烦恼直接解决了，嘻嘻。

当然，最后我还是想说一下我对各类过程的最经典定义的理解。

递归：显式函数自己显式地调用自己

循环：可重复执行自身零次或多次的代码段

迭代：由固定数目的旧变量推出等量新变量的收敛过程

递推：由离散序列已知初始值推出后续项的过程

遍历：逐次访问离散序列中的每一项的过程

注：定义中的“显式函数”，特指在编程语言中以函数/方法代码块（包括匿名函数等特殊函数代码块）形式明确定义的可执行实体。此限定旨在将编程中的递归调用，与一段代码在数学上可被理解为函数的情况区分开来。