递归如何转换为非递归

作者: veaxen 分类: 数据结构与算法 发布时间: 2017-04-07 14:17

递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。递归的特点包括:递归过程简洁、易编、易懂;递归过程效率低、重复计算多。

考虑递归的执行效率低,可以尝试将递归过程转换为非递归过程。本文就是来探讨怎么转换的。

将递归算法转换为非递归算法有两种方法,一种是直接求值(迭代/循环),不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法。

一、直接转换法

直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。

1.单向递归

简单的说是指递归的过程总是朝着一个方向进行,如果函数1调用了函数2,而函数2又调用了函数1,则这种情况不属于单向递归。斐波那契数列(单向递归)的递归求解可转用一个迭代法实现。

斐波那契数列的递归求解:

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

转换为迭代求解过程:

int Fib(int n) {
   if(n <= 1) return n;
  int twoBack = 0;
   int oneBack = 1;
   int cur;
  for(int i = 2;i < = n; i++) {
      cur = twoBack + oneBack;
    twoBack = oneBack;
      oneBack = cur;
   }
   return cur;
}

2.尾递归

是以递归调用结尾的函数,是单向递归的特例。它的递归调用语句只有一个,而且是放在过程的最后。当递归调用返回时,返回到上一层递归调用语句的下一语句,而这个位置正好是程序的结尾,因此递归工作栈中可以不保存返回地址;除了返回值和引用值外,其他参数和局部变量都不再需要,因此可以不用栈,直接采用循环写出非递归过程。

阶乘函数就不是一个尾递归。因为在它收到递归调用的结果后,必须在返回调用前再做一次乘法运算。但是阶乘函数可以转化成一个尾递归函数,例:

阶乘的递归求解:

int factorial(int n)
{
   if(n == 0) return 1;
   else{
    int val = factorial(n - 1);
    return n * val;
   }
}

转换为尾递归:

int factorial(int acc, int x)

 { //acc传的值为1。
  if(x <= 1) return acc;
  else

     return factorial(x * acc, x - 1);
}

尾递归的重要性在于当进行尾递归调用时,调用者的返回位置不需要被存在调用栈里。当递归调用返回时,它直接分支到先前已保存的返回地址。因此,在支持尾递归优化的编译器上,尾递归在时间和空间上都比较划算。迭代算法需要一个临时变量,这无疑导致了程序的可读性降低,迭代函数不像递归函数那样需要考虑函数调用的支出,而且对一个线程来说可用的栈空间通常比可用的堆空间要少得多,而递归算法则相对迭代算法需要更多的栈空间!

二、间接转换法

该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:

将初始状态s0进栈
while (栈不为空){
    退栈,将栈顶元素赋给s;
    ……
    ……
    if(不满足递归结束条件){
        寻找到s的相关状态s1;
        将s1进栈
  }
}

间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等,下面我们以二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。

1)前序遍历

a)递归方式:
void preorder_recursive(Bitree T)            /* 先序遍历二叉树的递归算法 */
{
    if (T) {
        visit(T);                /* 访问当前结点 */
        preorder_recursive(T->leftChild);  /* 访问左子树 */
        preorder_recursive(T->rightChild);  /* 访问右子树 */
    }
}
b)非递归方式
void preorder_nonrecursive(Bitree T)              /* 先序遍历二叉树的非递归算法 */
{
    initstack(S); //初始化栈

    push(S,T);                         /* 根指针进栈 */
    while(!stackempty(S)) {
        while(gettop(S,p)&&p) {           /* 次循环是向左走到尽头,其中gettop()获得栈顶*/
            visit(p);          /* 每向前走一步都访问当前结点 */
            push(S,p->leftChild);
        }
        pop(S,p);
        if(!stackempty(S)) {            /* 向右走一步 */
            pop(S,p);          /* 空指针退栈 */
            push(S,p->rightChild);
        }
    }
}

2)中序遍历

a)递归方式
void inorder_recursive(Bitree T)        /* 中序遍历二叉树的递归算法 */
{
    if (T) {
        inorder_recursive(T->leftChild);     /* 访问左子树 */
        visit(T);                /* 访问当前结点 */
        inorder_recursive(T->rigthChild);    /* 访问右子树 */
    }
}
b)非递归方式
void  inorder_nonrecursive(Bitree T)
{
initstack(S);                        /* 初始化栈 */

    push(S, T);                         /* 根指针入栈 */
    while (!stackempty(S)) {
        while (gettop(S, p) && p) /* 向左走到尽头 */
            push(S, p->leftChild);
        pop(S, p);                   /*向左走到尽头时,最后一个叶节点的leftChild是NULL,空指针退栈*/
        if (!stackempty(S)) {
            pop(S, p);
            visit(p);          /* 访问当前结点 */
            push(S, p->rightChild);     /* 向右走一步 */
        }
    }
}

3)后序遍历

a)递归方式
void postorder_recursive(Bitree T)           /* 中序遍历二叉树的递归算法 */
{
    if (T) {
        postorder_recursive(T->leftChild);  /* 访问左子树 */
        postorder_recursive(T->rightChild); /* 访问右子树 */
        visit(T);                        /* 访问当前结点 */
    }
}

b)非递归方式

typedef struct {
    BTNode* ptr;
    enum {0,1,2} mark;
} PMType;                               /* 有mark域的结点指针类型 */

void postorder_nonrecursive(BiTree T)    /* 后续遍历二叉树的非递归算法*/
{
    PMType a;
    initstack(S);                       /* S的元素为PMType类型 */

    push (S,{T,0});                  /* 根结点入栈 */
    while(!stackempty(S)) {
        pop(S,a);
        switch(a.mark){
            case 0:
                push(S,{a.ptr,1});       /* 修改mark域 */
                if(a.ptr->leftChild)
                    push(S,{a.ptr->leftChild,0}); /* 访问左子树 */
                break;
            case 1:
                push(S,{a.ptr,2});       /* 修改mark域 */
                if(a.ptr->rightChild)
                    push(S,{a.ptr->rightChild,0}); /* 访问右子树 */
                break;
            case 2:
                visit(a.ptr);           /* 访问结点 */
        }
    }
}

参考:
http://www.cnblogs.com/TECHNOLOGYer/p/4776496.html
http://blog.csdn.net/shunrei/article/details/5680579

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据