转载本文请联系原作者获取授权，同时请注明本文来自戚正伟科学网博客。

摘要：在数据结构的教学中，我们经常用到递归，例如广义表，二叉树等，但是在课本中讲到递归算法的非递归化却寥寥数语，并且很多学生也问到这个问题。该文针对这一情况研究递归函数的非递归化。该文根据是否是尾递归进行分类，重点讲解两种不同的非递归化方法，其中一种转换成循环来实现非递归化，但是对于复杂的非尾递归则使用栈来模拟系统栈的工作方式来实现非递归化，最后给出递归和非递归化的比较，根据问题的实际情况选择是否采用递归。

关键词：递归算法;非递归化;尾递归;迭代;非尾递归;栈

什么是递归？有这样一个非常典型的例子：从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是......递归函数就是一个直接调用自己或通过一系列的调用语句间接调用自己的函数。递归函数包含三种：第一，有很多递归定义的数学函数，例如阶乘，斐波那契数列;第二，有本身具有递归特性的数据结构，例如二叉树，广义表等;第三种有些问题递归求解比迭代求解更加简单，例如Hanoi塔问题，八皇后问题等。

此外，递归有三个要素：第一，递归边界条件：确定递归到何时终止，即递归出口;第二，递归模式：大问题如何分解为小问题的，即递归体;第三，递归的调用次数必须是有限的，每次递归调用后必须越来越接近某种限制条件。实际上，递归就是把不好解决的复杂问题分解为一个或多个小问题，再把这些小问题分解成更小的问题，直到每个小问题都可以直接解决。

在执行递归算法时，它包括递推和回归两个过程。在进行递推过程中，就是将大问题分解为若干小问题，再进行求解，且必须要有终止递归的条件;在进行回归时，得到小问题的解，并且依次返回，求得较大问题的解，最后取得最大问题的解。

递归使得程序简洁明了，理解起来比较轻松，但是递归算法中来回切换函数调用现场浪费时间，并且系统提供栈来保存执行现场需要大量的空间。首先，系统设立一个递归工作栈来保证递归函数的正确执行。该系统工作栈是递归函数运行期间使用的数据存储区。当调用一个递归函数时，系统会自动构建一个工作记录，称为栈帧，栈帧放在栈的最上面。开始的时候，栈帧仅仅存放返回地址和指向上一个帧的指针。每进入一层递归，就把新的记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录（即把栈帧删除），直到程序控制返回原调用函数。于是，递归实现的空间效率并不高，又因为频繁的压栈和出栈时间开销也非常大。总之，递归存在一个致命的缺点就是，递归的深度太深会导致堆栈溢出。

3 递归算法转换为非递归算法的典型案例

在教学过程中，很多同学都以为使用栈将递归算法转换为非递归算法，其实这种想法是错误的。递归算法分为尾递归和非尾递归。尾递归直接用循环来实现递归不需要栈来辅助，非尾递归则要使用栈来实现非递归算法。

（1）尾递归转换成非递归算法

尾递归就是当递归调用时最后执行的语句是递归语句并且函数体中包含递归体的返回值不是表达式的一部分。在回归的过程中，尾递归函数不需要任何操作。现在很多的编译器利用这一特点，使得代码得到优化。

尾递归的工作原理：当编译器检测到是尾递归函数调用时，每一层递归信息构成的工作记录就覆盖栈顶记录，不会增加递归的深度。于是，每进入一层递归，栈顶存放的就是最后一条准备执行的记录，这也就是说尾递归的栈的深度为1.但是这些并不是说明尾递归不需要栈，只是栈帧没有其他的事情可以做，所以可以用循环来实现非递归化。也就是说，每一次递归调用只需要覆盖栈帧，大大缩减了栈空间，所以非递归化时不需要手动的压栈和出栈，大大提高了运行的效率。

算法1：利用尾递归求最大公约数

算法2：利用循環求最大公约数

算法1：使用非尾递归实现n！

算法2：利用尾递归实现n！

算法3：利用循环实现非递归n！

从上面两个例子可以看出，实现尾递归往往需要改写递归函数，确保最后一步调用自身。要把普通的递归函数转换为尾递归函数就须把所有用到的内部变量改写成函数的参数。总之，凡是能改写成尾递归的函数在非递归化时，都能用循环实现。虽然有些函数可以改写成尾递归，但是在一定程度上降低了程序的可读性。

（2）非尾递归函数借助栈来实现非递归化

顾名思义，非尾递归是递归执行不是最后一句或属于表达式的一部分。对于非尾递归而言，递归的过程是编译器处理了压栈和出栈的操作，转换为迭代函数就需要手动地处理压栈和出栈。

算法1：利用递归算法实现汉诺塔问题

move（A，1，C）;//将编号为1的圆盘从A移到C

算法2：利用非递归算法实现汉诺塔问题

算法1：使用递归算法中序遍历二叉树

算法2：使用非递归算法中序遍历二叉树

if（p）{//根指针进栈，遍历左子树

else//根指针退栈，遍历右子树

4 递归算法与非递归算法的比较

由上述例子可以发现，递归方式设计的算法实现简洁，思路清晰，具有良好的可读性和可维护性，很容易证明该算法的正确性。但是，递归程序的执行效率一般低于非递归程序。尤其是递归深度较深时，就造成空间耗费大，这是递归算法最致命的弱点。

在要求执行效率比较高的情况下，我们一般选用非递归算法。根据尾递归的工作原理，递归所使用的栈空间就很大程度的缩减了，运行当中虽然利用到了堆栈，但是栈的深度为1。这样在转化为非递归化函数时，利用迭代就可以实现非递归化，这样运行效率会变得很高。非尾遞归利用栈来实现递归的非递归化，手动的压栈和出栈，难于编写，出错率高。理论上，递归算法一般可转化为非递归算法，但是有一些算法很难实现非递归化，所以要根据实际情况选择是递归还是非递归。

在数据结构的教学中，递归算法的非递归化一直是教学中的重点和难点。在遇到一个问题时，要根据具体情况具体分析看是否使用递归算法。本文首先分析递归的特点，然后分析递归转化为非递归的两种方式，使学生很容易掌握递归函数的非递归化。

[1] 李莹，孙承福.数据结构[M].北京：清华大学出版社，2013.

[2] 高汉平，方志雄.从递归算法到非递归的变换[J].黄冈师范学院学报，2002，22（3）：47-50.

[3] 施伯乐，等.数据结构[M].上海：复旦大学出版社，1988.

[4] 孟林，尹德辉.递归算法本质及非递化的一般规律[J].福建电脑，2004，20（1）：12-46.

[6] 周法国，韩智，高天.递归算法设计思想与策略分析[J].软件导刊，2017，16（10）：35-38.

[7] 李云鹤，武善玉，钟鸣.最优二叉树编译码确定的一种新方法[J].茂名学院学报，2003，13（4）：42-44，64.

[8] 高鹭，周李涌.递归算法及其转化为非递归算法的分析[J].科技资讯，2008，6（30）：210.

[9] 姚俊明，邢丹，厉群，等.数据结构课程中递归教学的深入探讨[J].电脑知识与技术，2011，7（14）：，3385.

本篇介绍的不是什么新知识，而是对前面讲解的一些知识的综合运用。众所周知，递归是解决复杂问题的一个很有效的方式，也是函数式语言的核心，在一些函数式语言中，是没有迭代与while这种概念的，因为此类的循环通通可以用递归来实现，这类语言的编译器都对递归的尾递归形式进行了优化，而的编译器并没有这样的优化，本篇就要完成这样一个对于尾递归的优化。

本篇将使用递归中最简单的阶乘计算来作为例子

这种方法计算阶乘比较大的数很容易就栈溢出了，原因是每次调用下一轮递归的时候在栈中都需要保存之前的变量，所以整个栈结构类似是这样的

在没有递归到底之前，那些中间变量会一直保存着，因此每一次递归都需要开辟一个新的栈空间

任何递归的尾递归版本都十分简单，分析上面栈溢出的原因就是在每次return的时候都会附带一个变量，因此只需要在return的时候不附带这个变量即可。说起来简单，该怎么做呢?其实也很容易，我们使用一个参数来保存上一轮递归的结果，这样就可以了，因此尾递归的阶乘实现应该是这样的代码。

这样子通过每轮递归结束后刷新当前的栈空间，复用了栈，就克服了递归的栈溢出问题，像这样的return后面不附带任何变量的递归写法，也就是递归发生在函数最尾部,我们称之为'尾递归'。

使用lambda实现编译器的优化

很显然，如果事情这么简单的话，这篇文章也就结束了，和lambda也没啥关系 :) 然而当你调用上文的尾递归写法之后，发现并没有什么作用，该栈溢出的还是会栈溢出，其实原因我在开头就已经说了，尾递归这样的写法本身并不会有什么用，依赖的是编译器对尾递归写法的优化，在很多语言中编译器都对尾递归有优化，然而这些语言中并不包括java，因此在这里我们使用lambda的懒加载(惰性求值)机制来延迟递归的调用，从而实现栈帧的复用。

因此我们需要设计一个这样的函数接口来代替递归中的栈帧，通过apply这个函数方法(取名叫apply是因为该方法的参数是一个栈帧，返回值也是一个栈帧,类比function接口的apply)完成每个栈帧之间的连接，除此之外，我们栈帧还需要定义几个方法来丰富这个尾递归的接口。

• apply（连接栈帧，惰性求值）

根据上面的几条定义,设计出如下的尾递归接口

设计对外统一的尾递归包装类

为了达到可以复用的效果,这里设计一个尾递归的包装类,目的是用于对外统一方法,使得需要尾递归的调用同样的方法即可完成尾递归,不需要考虑内部实现细节，因为所有的递归方法无非只有2类类型的元素组成,一个是怎样调用下次递归,另外一个是递归的终止条件，因此包装方法设计为以下两个

通过使用上面的尾递归接口与包装类,只需要调用包装了call与done就可以很轻易的写出尾递归函数,代码如下

通过观察发现,和原先预想的尾递归方法几乎一模一样,只是使用包装类的call与done方法来表示递归的调用与结束


这里作一个说明,因为阶乘的计算如果要计算到栈溢出一般情况下Java的数据类型需要使用BigInteger来包装,为了简化代码，这里的测试仅仅是是测试栈会不会溢出的问题,因此我们将操作符的*改成+这样修改的结果仅仅是结果变小了,但是栈的深度却没有改变。测试代码如下
首先测试 深度为10W的普通递归

这里我们测试1000W栈帧的尾递归

由于阶乘的计算一般初始值都为1,所以再进一步包装一下,将初始值设置为1

最终调用代码如下,完全屏蔽了尾递归的实现细节

本文讲解了利用lambda懒加载的特性完成了递归中栈帧的复用,实现了函数式语言编译器的'尾递归'优化,虽然上面的例子很简单，但是设计的接口和包装类都是通用的，可以说任何需要使用尾递归的都可以使用上面的代码来实现尾递归的优化，这也算是为编译器帮了点忙吧。

本文永久更新链接地址：