递归如何转换为⾮递归
递归算法实际上是⼀种分⽽治之的⽅法，它把复杂问题分解为简单问题来求解。递归的特点包括：递归过程简洁、易编、易懂；递归过程效率低、重复计算多。
考虑递归的执⾏效率低，可以尝试将递归过程转换为⾮递归过程。本⽂就是来探讨怎么转换的。
将递归算法转换为⾮递归算法有两种⽅法，⼀种是直接求值（迭代/循环），不需要回溯；另⼀种是不能直接求值，需要回溯。前者使⽤⼀些变量保存中间结果，称为直接转换法；后者使⽤栈保存中间结果，称为间接转换法，下⾯分别讨论这两种⽅法。
⼀、直接转换法
直接转换法通常⽤来消除尾递归和单向递归，将递归结构⽤循环结构来替代。
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);          /* 访问结点 */
}
}
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。