递归和非递归的转换
在第一讲《算法设计之枚举法》中我们有一道练习题：
例6：构造一个3*3的魔方：把数字1-9添入如图的表格中
|
2 |
7 |
6 |
|
9 |
5 |
1 |
|
4 |
3 |
8 |
要求每横，竖，斜列之和均相等（如图是一种情况）。输出所有可能的魔方。
当时我们是使用枚举法解的，通过剪枝等优化后得到一个8重嵌套循环，而且每个循环的结构都是一样的，既繁琐，又复杂。既然如此，那么我们是否可以用一个递归函数来实现呢？答案是肯定的。程序如下：
#include<stdio.h>
#define MAX 9
int IsElement(int a[], int len, int x);
void F(int a[], int len);
int main()
{
int a[MAX] = {0};
int i;
for (a[0]=1; a[0]<=MAX; a[0]++)
{
F(a, 0);
}
getchar();
return 0;
}
void F(int a[], int len)//以递归代替多重嵌套循环
{
int i;
if (len < MAX-2 && IsElement(a, len, a[len]))
{
len++;
for (a[len]=1; a[len]<=9; a[len]++)
{
F(a, len);
}
}
else if (len == MAX-2)
{
a[8] = 45-a[0]-a[1]-a[2]-a[3]-a[4]-a[5]-a[6]-a[7];
if ((a[0]+a[1]+a[2]) == (a[3]+a[4]+a[5]) && (a[0]+a[1]+a[2]) == (a[6]+a[7]+a[8])
&& (a[0]+a[3]+a[6]) == (a[1]+a[4]+a[7]) && (a[0]+a[3]+a[6]) == (a[2]+a[5]+a[8])
&& (a[0]+a[1]+a[2]) == (a[0]+a[4]+a[8]) && (a[0]+a[1]+a[2]) == (a[2]+a[4]+a[6]))
{
for (i=0; i<9; i++)
{
printf("%5d", a[i]);
if ((i+1)%3 == 0)
printf("\n");
}
printf("\n\n");
}
}
}
int IsElement(int a[], int len, int x)
{
int i;
for (i=0; i<len; i++)
{
if (a[i] == x)
return 0;
}
return 1;
}
从本例中我们可以发现，用递归代替多重嵌套循环不仅使程序结构清晰,可读性强,且容易用数学规纳法证明算法的正确性,因此设计算法与调试程序都很方便。
实际上，递归是软件设计中的一种重要的方法和技术．递归函数是通过调用自身来完成与自身要求相同的子问题的求解，编译系统能自动实现调用过程中信息的保存与恢复．在问题的求解方法具有递归特征时，采用递归技术就比不用递归技术简捷得多，且具有较高的开发效率，所设计的程序具有更好的可读性和可维护性．然而，在实际应用中，由于程序设计语言对递归的支持性和程序运行时间方面的原因，在有些情况下要求写出问题的非递归函数．由于许多问题求解程序中的递归函数比非递归函数要容易设计，因此，常常先设计出递归函数，然后将其转换为等价的非递归函数．
要向实现递归和非递归函数的相互转换，我们先要了解递归调用的内部实现原理。
在调用一个函数的过程中出现直接或间接的调用该函数本身，称为函数的递归调用．与每次调用相关的一个重要概念是递归函数运行的“层次”．设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第i层递归调用本函数为进入“下一层”，即第i+1层．反之，退出第i层递归应返回至“上一层”，即第i-1层．因此，编译系统需设立一个“工作栈”来进行调用函数和被调函数之间的链接和信息交换．设工作栈开始时为空，则递归调用内部实现描述如下：
1)调用时需执行的操作
a．将返回地址、调用层(第i层)中的形参和局部变量的值压人工作栈中(第0层调用不考虑)；
b．为被调层(第i+1层)准备数据：计算实在参数的值，并赋予对应的形参；
C．转入被调函数执行．
2)函数返回时需执行的操作
a．如果函数有返回值，将返回值保存到一临时变量中；
b．从栈顶取出返回地址及各变量、形参的值，并退栈，即恢复调用层(第i-1层)的局部变量和形参；
c．按返回地址返回到调用层(第i-1层)；
d．返回后自动执行如下操作：如函数有返回值，则从临时变量中取出返回值赋予调用层(第i-1层)相应的局部变量或代人表达式中．
了解了内部实现原理，现在我们来看由递归到非递归的转换规则。既然编译系统内部是利用“工作栈”这种数据结构来实现递归函数的，因此，递归函数用非递归函数实现时也必然要用“栈”来保存相应的形参和局部变量．通过仔细研究编译系统内部实现递归函数的工作原理，得到转换规则如下：
1)设置一个工作栈，用S表示，并在开始时将其初始化为空．
2)在递归函数的人口处设置一个标号(如设为L0)．
3)对递归函数中的每一个递归调用，用以下几个等价操作来替换：
a．保留现场：开辟栈顶存储空间，用于保存调用层中的形参、局部变量的值和返回地址；
b．准备数据：为被调层准备数据，即计算实参的值，并赋予对应的形参；
C．转入(递归函数)执行，即goto L0；
d．在返回处设一个标号Li(i一1，2，3，⋯)，并根据需要设置以下语句：如果递归函数有返回值，则增设一个变量保存回传变量返回的值．
4)在返回语句前判断栈空否，如果栈不空，则依次增加如下操作：
a．回传数据：若函数有返回值，增设一个变量，将返回值保存到该变量(称回传变量)中；
b．恢复现场：从栈顶取出返回地址(不妨保存到Lx中)及各变量、形参的值，并退栈；
C．返回：按返回地址返回(即执行goto X)．
5)对其中的非递归调用和返回语句照抄．
6)如果递归程序中只有一处递归调用，则在转换时，返回地址不必入栈．
7)在模拟尾递归调用时，不必执行入栈操作．
注 尾递归即递归调用处于递归函数的最后位置，其后面没有其他操作．
用上述规则可将任意的递归函数转换为等价的非递归函数．不过，转换得到的函数的结构一般比较差，因而需要重新调整．
转换规则看上去很复杂，其实我们可以理解得简单些，求解递归问题有两种方式，一种是直接求值，不需要回溯的；另一种是不能直接求值，需要回溯的。这两种方式在转换成非递归问题时采用的方法也不相同。前者使用一些中间变量保存中间结果，称之为直接转换法（即转换成迭代算法）；后者需要回溯，所以要用栈保存中间结果，称为间接转换法。下面分别讨论这两种方法。
直接转换法
仍然以斐波那契(Fibonacci)数列为例，前面我们介绍了斐波那契(Fibonacci)数列的递归算法，发现该算法虽然代码短小精悍，可读性强，但是由于做了大量的重复运算，使得效率极为低下，所以应该转换成非递归算法。斐波那契(Fibonacci)数列的非递归算法即迭代法，我们在第2讲《算法设计之迭代法》中已经做了详细解释，这里不再重复。
我们看一个其他的例子：
例7：逆序打印数字。例如考虑如何打印数字1369。我们首先需要打印9，然后打印6，再打印3，最后打印1。
很明显我们可以把问题看成是先打印1369的个位数字，然后打印136的个位数字，然后打印13的个位数字，最后打印1的个位数字。一个很典型的递归问题。
#include<stdio.h>
void PrintInt(int n);
int main()
{
int n = 138400;
PrintInt(n);
getchar();
return 0;
}
void PrintInt(int n)
{
printf("%d", n%10);
if (n >= 10)
PrintInt(n/10);
}
同时我们可以发现，递归函数中使用了尾递归（仅在方法的末尾实行一次递归调用，这样的递归叫尾递归）。尾递归很容易被循环所替换，下面是使用循环的写法。
void PrintInt(int n)
{
while (n > 0)
{
printf("%d", n%10);
n /= 10;
}
}
这个例子实在是太简单，下面我们看一个稍微复杂点的例子。
例8：逆序排列数组。例如原数组为a[] = {1，2，3，4，5}，经过逆序排列后变成a[] = {5，4，3，2，1}。经典的逆序排列算法是使用循环。
void Reverse(int a[], int len)
{
int l, r;
int temp;
for (l=0,r=len-1; l<r; l++,r--)
{
temp = a[l];
a[l] = a[r];
a[r] = temp;
}
}
实际上我们可以看到逆置数组的操作是一个从两端到中间，规模逐渐减小的过程，每次交换元素a[i]和a[n-i]，动作完全是一样的，所以也可以使用递归算法。
void Reverse(int a[], int len)
{
Rev(a, 0, len-1);
}
void Rev(int a[], int left, int right)
{
int temp;
if (left < right)
{
temp = a[left];
a[left] = a[right];
a[right] = temp;
Rev(a, left+1, right-1);
}
}
这里的递归函数是Rev，为了保证同循环算法的接口保持一致，我们把函数Reverse作为Rev的驱动函数，这在比较复杂的递归算法中是很常见的。
间接转换法
前面讲了一个逆序打印数字的例子，现在来看一个与它类似的例子:
例9：以任意基数打印数字。例如考虑如何打印数字1369。我们首先需要打印1，然后打印3，再打印6，最后打印9。问题是获得首位麻烦，给定数字n，我们需要循环确定n的首位。与之相反的是末位，利用n%10就可以得到它。
用递归实现这个例程是非常简单的：
#include<stdio.h>
void PrintInt(int n, int base);
int main()
{
int n = 100;
int base = 2;
PrintInt(n, base);
getchar();
return 0;
}
void PrintInt(int n, int base)//n表示被输出的十进制数，base表示被输出的数的基数，即进制，
{
if (n >= base) //这里要求base <= 10
PrintInt(n/base, base);
printf("%d", n%base);
}
但是使用非递归方式就没那么简单了，这不比上一题，这里不是尾递归，不能直接转换，必须先用栈把得到的数字存储起来，再一次性输出。程序如下：
void PrintInt(int n, int base)//n表示被输出的十进制数，base表示被输出的数的基数，即进制，
{
int a[50] = {0}; //假设n的最大位数为50
int i = 0;
while (n > 0)//用栈把得到的数字存储起来
{
a[i++] = n % base;
n /= base;
}
while (i > 0)//逆序输出栈的元素
{
printf("%d", a[--i]);
}
}
二叉树数据结构是一种典型的递归定义和递归操作的数据结构，涉及到很多递归算法，现在我们来看一个简单的二叉树算法：前序遍历二叉树。
链接存储的二杈树类型和结构定义如下：
typedef struct bnode
{
ElemType data;
struct bnode *lchild, *rchild;
} btree;
1．递归算法非常简明：
void preorder(btree *p)
{
if(p != NULL)
{
printf("%d", p->data);//输出该结点（根结点）
preorder(p->lchild); //遍历左子树
preorder(p->rchild);//遍历右子树
}
}
2．非递归算法（使用栈存储树）：
void preorder(btree *bt)
{
btree *p, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int top=0;
if(bt != NULL)//先判断是否为空树
{
stack[top] = bt; //根结点入栈
while(top >= 0)
{
p = stack[top--]; //栈顶元素出栈
printf("%d", p->data);//输出该结点
if(p->rchild != NULL) //如果该结点有右孩子，将右孩子入栈
{
stack[++top] = p->rchild;
}
if(p->lchild != NULL) //如果该结点有左孩子，将左孩子入栈，按照后入先出原则，左孩子先出栈
{
stack[++top] = p->lchild;
}
}
}
}
或者：
void preorder(btree *bt)
{
btree *p, *stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int top=0;
if(bt != NULL)//先判断是否为空树
{
p = bt;
while (p || top > 0)
{
if (p)
{
stack[top++] = p;
printf("%c", p->data);//输出该结点
p = p->lchild;
}
else
{
p = stack[--top]; //栈顶元素出栈
p = p->rchild;
}
}
}
}
总结：递归算法既是一种有效的算法设计方法，也是一种有效的分析问题的方法。递归算法求解问题的基本思想是：对于一个较为复杂的问题，把原问题分解成若干个相对简单且类同的子问题,这样，原问题就可递推得到解。
适宜于用递归算法求解的问题的充分必要条件是：
（1）问题具有某种可借用的类同自身的子问题描述的性质；
（2）某一有限步的子问题（也称作本原问题）有直接的解存在。
当一个问题存在上述两个基本要素时，该问题的递归算法的设计方法是：
（1）把对原问题的求解设计成包含有对子问题求解的形式。
（2）设计递归出口。
评论