递归算法到非递归算法的转换

递归实质在定义自身的同时又出现了对自身的调用。递归算法是许多软件编程人员常用的方法，结构简单、清晰、可读性好。但在实际应用中也存在一些问题：1.并不是每一门语言都支持递归，比较典型的FORTRAN语言，它明确规定了不允许直接或间接使用递归；2.递归算法在执行过程中会消耗太多的时间和空间。而在实际设计程序过程中，递归程序比非递归程序要容易设计，因此在许多情况下，常常是先设计出递归程序，然后再将其转换成等价的非递归程序。

1.基于循环结构的递归消除

可利用循环结构进行递归消除的递归有两种情况：尾递归和单向递归。

尾递归即递归调用语句只有一个，而且处于算法的最后。单向递归，即递归函数中虽然有一处以上的递归调用语句，但个递归调用语句的参数只与主调函数有关，相互之间参数无关，并且这些递归调用语句处于算法的最后。对于尾递归和单向递归的递归消除各举一个例子进行说明。典型的尾递归例子是求 N! (阶乘)算法。

算法为：

int fac（int n）{　　
　　if（n= =0 || n= =1）
　　　　return 1;
　　return n* fac（n-1）;
}

分析算法可知，3!的递归依赖关系为，fac（3）→fac（2）→fac(1) →fac(0)，因此可以利用循环结构直接从 fac（0）开始计算，一直循环到 fac（3）即可。

算法为：

int fac( int n){
　　int fac=1;
　　for (int i=1;i<=n; i++)
　　　　fac=fac* i ;
　　return fac;
}

典型的单向递归的例子是求斐波那契数列的 Fib（n）算法。

算法为：

int Fib ( int n )
{
　　if ( n <= 1 )
　　　　return n;
　　else
　　　　 return Fib (n-1) + Fib (n-2);
}

分析算法可知，Fab（5）的依赖关系如图 1 所示。因此，由图可知，可从下向上依次循环即可求得 Fib(5)。

算法为：

int Fib( int n )
{
　　 int x , y , z ;
　　if ( n= =0 || n= =1) 　
　　　　return n;
　　else
　　{
　　　　x=0 , y=1;
　　　　for (i=2;i<=n; i++)
　　　　{
　　　　　　z=y;
　　　　　　y=x+y;
　　　　　　x=z;
　　　　}
　　}
　　return y;
}

2.二叉树遍历

二叉树的非递归遍历是利用模拟栈的方法来实现非递归性递归的转换。遍历分为前序，中序和后序三种，一棵二叉树的三种遍历过程的遍历路线相同，都是从左到右，但是遍历的结果不同。对于每种遍历，树中的结点都经历三次，但是前序遍历在第一次遇到节点时立即访问，而中序遍历是在第二次遇到节点时才访问，后序遍历在第三次遇到时才访问。以下是三种遍历的算法(其中前序和中序基本一致，固写在同一算法中)

1）前序遍历

递归遍历：

void PreOrder(BiTree T)
{
　　if(T!=NULL)
　　{
　　　　visit(T);
　　　　PreOrder(T->lchild);
　　　　PreOrder(T->rchild);
　　}
}

非递归遍历：

void PreOrder(Bi Tree *root,(*visit)())
{
　　InitStack(s);//置空栈
　　p=root;
　　while(p! =Null||! stackempyt(s))
　　{
　　　　if(p! =Null)
　　　　{
　　　　　　Visit(p);
　　　　　　Push（s,p）；
　　　　　　p=p->lchild;
　　　　}
　　　　else(! stackempty(s))
　　　　{
　　　　　　Pop(s,p);
　　　　　　p=p->rchild;
　　　　}
　　}
}

2）中序遍历

中序递归遍历：

void InOrder(BiTree T)
{
　　if(T!=NULL)
　　{
　　　　　　InOrder(T->lchild);
　　　　　　visit(T);
　　　　　　InOrder(T->rchild);
　　}
}

中序非递归遍历：

算法思想：可以借助栈，将二叉树的递归算法转换为非递归算法，先扫描（并非访问）根结点的所有结点，并将他们一一进栈。然后出栈一个结点p（显然p结点没有左孩子结点或者左孩子结点已经被访问过），则访问他。然后扫描该结点的右孩子结点，将其进栈，再扫描该右孩子结点的所有左结点并一一进栈，如此继续，直到栈空为止。

void InOrder(Bi Tree *root,(*visit)())
{
　　InitStack(s);//置空栈
　　p=root;
　　while(p! =Null||! stackempyt(s))
　　{
　　　　if(p! =Null)
　　　　{
　　　　　　Push（s,p）；
　　　　　　p=p->lchild;
　　　　}
　　　　else(! stackempty(s))
　　　　{
　　　　　　Pop(s,p);
　　　　　　visit(p);
　　　　　　p=p->rchild;
　　　　}
　　}
}

3）后序遍历

后序递归遍历：

void PostOrder(BiTree T)
{
　　if(T!=NULL)
　　{
　　　　　　PostOrder(T->lchild);
　　　　　　PostOrder(T->rchild);
　　　　　　visit(T);
　　}
}

后序非递归遍历：

算法思想：因为后续遍历递归二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用堆栈来存储结点，必须分清返回根节点时，是从左子树返回的还是从右子树返回的。所以使用辅助指针人，其指向最近访问过的结点，也可以在结点中增加一个标志域，记录是否被访问过。

void PostOrder(BiTree T){
    InitStack(s);
    p=T;
    r=NULL;
    while(p||!IsEmpty(s)){
        if(p){//向左
            push(S,p);
            p=p->lchild;//重置p指针，左子树
        }
        else{//向右
            GetTop(S,p);
            if(p->rchild &&p->rchild!=r){//右子树存在，且未被访问过
                p=p->rchild;
                push(S,p);
                p=p->lchild;//重置p指针，右子树
            }
            else{//满足后序遍历时访问结点条件
                pop(S,p);
                visit(p->data);
                r=p;//记录最近访问的结点
                p=NULL;//重置p指针，不需要左子树，需要栈顶元素
            }
        }
    } 
}

3.利用二叉树的非递归遍历来消除递归

依靠二叉树的非递归算法也可实现递归向非递归的转换，因为递归程序都可以用树结构表示，最后都转化为二叉树的遍历问题。总的来说，转换基本原理和二叉树遍历的非递归实现一样还是基于栈来消除递归。因此确定问题的递归调用树，用树遍历的非递归算法来改进程序，就能达到递归向非递归的转换了。举例来说，对于斐波那契数列，递归定义为:

调用二叉树如图 2 所示。如图 2，求斐波那契数列 Fib(5)的非递归算法就是采用后序遍历二叉树的方法来遍历斐波那契数列的调用二叉树，凡是 visit 的部分替换成调用 Fib 函数即可。对于其它的递归算法也可以采用同样的办法，先画出调用二叉树，然后根据实际情况，判断采用何种非递归遍历，则利用二叉树的非递归调用方法可完成递归向非递归的转变。

参考：《递归到非递归算法的转换》崔蕊（南阳师范学院计算机与信息技术学院，河南南阳 473061）

　　　《王道——数据结构联考复习指导》王道论坛组编