递归算法的非递归化剖析

陈韶钰 孙娟

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

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

中图分类号：TP3        文献标识码：A

文章编号：1009-3044（2021）13-0202-03

1 递归算法的概述

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

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

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

2 递归算法的特点

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

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

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

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

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

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

例1：求最大公约数

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

int gcd1（int big，int small）

{

if（big%small==0）

return  small;

else

Return gcd（small，big%small）;

}

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

int gcd2（int a，int b）

{

while（b）

{

int t=a%b;

a=b;

b=t;

}

return a;

}

例2：求解n！

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

int jiecheng3（int n）

{

if（n==0||n==1）

return 1;

else

return n*jiecheng3（n-1）;

}

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

int jiecheng（int n，int a）

{

return （n==1）？a：jiecheng（n-1，n*a）;

}

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

int jiecheng2（int n）

{

int result=1;

if（n<0）

return 0;

else if（n==0||n==1）

return 1;

int i=1;

While（n>=i）

{

result=result*i;

i++;

}

}

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

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

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

例3：n阶汉诺塔问题

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

Void move（char from，int n，char to）

{

println（n+”号”+”from”+from+”to”+to）;

}

void hanoi（int n，char A，char B，char C）

{

if（n==1）

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

else{

hanoi（n-1，A，C，B）;//将编号为n-1的圆盘，借助C盘从A移到B

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

hanoi（n-1，B，A，C）;//将编号为n-1的圆盘，借助A盘从B移到A

}

}

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

struct act{

int num;

char x，y，z;

}s[max];

void hanoi（int n，char a，char b，char c）

{

int top=-1，count=0;

While（）

{

if（n>0）{//将编号为n-1的圆盘，借助C盘从A移到B

s[++top].num=n--;

s[top].x=a;

s[top].y=b;

s[top].z=c;

a=s[top].x;

b=s[top].y;

c=s[top].z;

}

else{

println（“%d：%d%c->%c”，++count，s[top].num，s[top].x，s[top].z）;//将编号n的圆盘从A移到C

n=s[top].num-1;//将编号为n-1的圆盘，借助A盘从B移到A

a=s[top].y;

b=s[top].x;

c=s[top].z;

top--;

}

}

}

例4：中序遍历二叉树

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

void inordertraverse（BiTree t）

{

if（t）

{

inordertraverse（ t->leftchild）;//遍历左子树

visit（t->data）;

inordertraverse（ t->rightchild）;//遍历右子树

}

}

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

void inordertraverse（BiTree  t）

{

Initstack（s）;

BiTree p=t;

while（p||！StackEmpty（s））{

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

Push（s，p）;

p=p->leftchild;

}

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

{

Pop（s，p）;

visit（p->data）;

p=p->rightchild;

}

}

return;

}

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

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

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

5 结束语

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

参考文献：

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

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

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

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

[5] 高大鹏.C语言教学中的语言技巧[J].科技信息，2012（27）：217，525.

[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）：3382-3383，3385.

【通联编辑：代影】