递归如何转换为非递归

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

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

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

一、直接转换法

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

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.htmlhttp://blog.csdn.net/shunrei/article/details/5680579

转载于:https://www.cnblogs.com/veaxen/p/9185581.html

相关资源：数据结构—成绩单生成器