递归程序是一种神奇的程序，我在开始学编程的时候就对递归程序很着迷。 这里我从“递归程序非递归化”等的角度对递归程序及其相关算法进行了分析，希望对大家 理解一些重要的计算机算法有帮助。由于以下的内容涉及许多算法设计的内容（比如： 回溯-迭代回溯策略，分支界限-广度优先策略，递归-分治策略等），所以建议具有程序员左右 水平的人阅读。当然，如果你是一个c语言和算法设计的初学者并且也能够读懂的话，我将十分的恭喜你，因为你有能力参加程序员甚至软件设计师考试了。 我们都知道：递归程序虽然在表达上非常简洁，但它的执行效率实却远远比同类其他算法低，所以将递归程序改为非递归程序将极大的改善程序的执行效率，或者干脆用其他算法（比如回溯，贪心，动态规划等）代替递归算法，下面四个例子是我心血的结晶：

例一：这个程序中采用不同的算法实现组合算法（从m个数中取k个数并列出所有这些数的组合），编写这个程序是在我看到一位版主在“c语言论坛”发的一个名为：“[穷举法]数学里的组合”的帖子以后才有感而发的。关于“穷举法”我不想多说，大家看了那个帖子就明白了。

/*以下程序在TC2.0编译！*/ #include <stdio.h> #define MAXN 100

#define M 5 /*默认为5选3（可以改为其他）*/ #define K 3

int a[MAXN]; /*暂时保存结果*/ int stack[MAXN]; /*定义栈*/ int top;

/*以下采用“递归-分治策略”实现组合算法（这个算法的效率比较低）*/ void comb(int m,int k) { /*comb函数不是我编的，是从我以前的高程教材中找出来的*/ int i,j; for(i=m;i>=k;i--) { a[k]=i; if(k>1) comb(i-1,k-1); else { for(j=a[0];j>0;j--) printf("%4d",a[j]); printf("\n"); } } }

/*以下函数是用“非递归化while-if形式”对comb函数进行单纯转化得到的,比comb的效率高*/ void comb_w_if(int m,int k) { int i; top=0; while(m>=k||top) { /*从comb函数可以看出：递归执行条件为：m>=k||top*/ if(m>=k) { a[k]=m; if(k>1) {stack[top++]=m--; --k;} /*进栈，改变参数。（从comb函数中看出递归体执行条件为：m>=k&&k>1）*/ else { /*否则为递归结束条件*/ for(i=a[0];i>0;i--) printf("%4d",a[i]); /*打印结果*/ printf("\n"); --m; /*--m：参数（递归体）回溯*/ } }else {m=stack[--top]-1; ++k;} /*满足回溯条件：出栈，恢复参数*/ } }

/*以下用”while-while形式“对comb函数进行单纯转化得到的*/ void comb_w_w(int m,int k) { /*该函数（及上面的函数）最大栈深为m-k，效果相当不错！*/ int i; top=0; while(m>=k||top) { while(m>=k) { a[k]=m; if(k>1) stack[top++]=m--,--k; else { for(i=a[0];i>0;i--) printf("%4d",a[i]); printf("\n"); --m; } } if(top) m=stack[--top]-1,++k; } }

/*以下函数是用”回溯-迭代回溯策略“实现，算法的效率很高（在组合算法中应当是一流的）,且不需要栈的支持,是我在这个学期编的最经典的算法！理解这个算法要把组合问题的解空间树画出来，因为整个算法都在解空间树上进行*/ void comb_dd(int m,int k) { int i=1,j; if(m<k) return; while(i>0) { /*i为解空间树的高度*/ a[i]=m; if(i==k) { /*搜索达到“预定”深度*/ for(j=1;j<=a[0];j++) printf("%4d",a[j]); /*输出结果*/ printf("\n"); while(a[i]==k-i+1) --i; /*从树的底层回溯*/ if(i!=k) m=a[i]-1; else --m; }else {++i;--m;} /*继续搜索（深度优先）*/ } }

/*comb_fz函数采用“分支界限-广度优先策略”编写，效率一般，但可以帮助理解 ”广度优先策略“，推荐!!*/ void comb_fz(int m,int k) { struct{ int data; int parent; int level; }queue[10*MAXN]; /*定义队列：parent记录父结点，level记录树的层数（深度）*/ int front=0,rear=0; int i,t,data,parent,level; if(m<k) return; for(i=m-k+1,t=m;i>0;--i,--t) { /*初始化队列*/ queue[rear].data=t; queue[rear].parent=-1; queue[rear].level=1; ++rear; } while(rear!=front) { data=queue[front].data; /*出队*/ level=queue[front].level; ++front; if(level==k) { /*输出结果*/ printf("%4d",data); parent=queue[front-1].parent; while(parent!=-1) { data=queue[parent].data; printf("%4d",data); parent=queue[parent].parent; } printf("\n"); } else { /*扩展：进行广度搜索*/ t=data-m-k+1; /*t定义了搜索范围*/ if(t<1) t=1; while(--data>=t) { queue[rear].data=data; queue[rear].parent=front-1; queue[rear].level=level+1; ++rear; } } } }

main() { a[0]=K; /*a[0]为组合个数：k*/ printf("comb output:\n"); comb(M,K); getch(); printf("comb_w_if output:\n"); comb_w_if(M,K); getch(); printf("comb_w_w output:\n"); comb_w_w(M,K); getch(); printf("comb_dd output:\n"); comb_dd(M,K); getch(); printf("comb_fz output:\n"); comb_fz(M,K); printf("End! Remember STN_LCD!"); getch(); }

对于”回溯算法“和”分支界限算法“我就不多说了（几句话也说不清楚）。 今天的主题是”递归程序非递归化”的问题，理解非递归化方法对我们理解和设计递归程序有很大的帮助。我们在理解递归程序时，不要沿着递归程序的语句去想象程序执行递归的过程，我们只需要找到他的"递归执行条件"：可能进入递归循环的条件；"递归体执行条件"：执行递归语句的条件；"递归回退条件"：一般与"递归体执行条件"相反,和"递归回退执行语句"：从递归返回以后要执行那些语句，就可以了，具体如何找要根据实际情况，没有什么定式！ 在进行非递归化的过程中，涉及到用栈保存参数的问题，许多书都说:”用栈保存所有的参数”，比如上面的comb_w_w函数要保存m和k参数，我们看到过的许多非递归化程序中也的确如此，但事实上跟本不需要保存这么多的参数：如果所有参数都要保存的话，非递归化程序的效率优势如何体现！ 在非递归化程序中，栈具有“栈顶跟踪”（自创名词）的特性：栈顶总是保存“当前处理参数”的父结点参数（栈顶一直跟踪当前的参数），我们可以利用这个特性简化非递归程序中的“参数栈”，一般都可以简化到一个参数，比如上面的comb_w_w和comb_w_if函数中的栈stack只保存了参数m,而另一个参数k就可以跟踪m的变化而不必用栈保存它了！为了验证我的结论，下帖是我编写的”汉诺塔“非递归化程序（相信大家都没见过吧）：

例二：”汉诺塔“非递归化程序

/*以下程序在TC2.0下编译*/ #include<stdio.h> int stack[100]; /*定义栈，栈中只保存一个参数：n*/ int top; int c=0;

void move(char x,int n,char z) { printf("Step%i: Put %i From %c to %c.\n",++c,n,x,z); } /*经典程序”汉诺塔“的递归形式：采用分治算法*/ void hanoi(int n,char x,char y,char z) { if(n==1) move(x,1,z); else { hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); } }

void hanoi_w_if(int n,char x,char y,char z) { /*用“while-if形式”改写hanoi的函数*/ char t; top=0; while(n>1||top) { if(n>1) { stack[top++]=n--; t=y; y=z; z=t; /*栈中只保存参数n,栈顶跟踪参数n从而确定参数x,y,z*/ } else { move(x,1,z); n=stack[--top]; t=y; y=z; z=t; move(x,n,z); --n; t=x; x=y; y=t; } } if(n==1) move(x,1,z); /*这句不能省了*/ }

void hanoi_w_w(int n,char x,char y,char z) { /*用“while-while形式”改写hanoi的函数*/ char t; top=0; while(n>1||top) { while(n>1) { stack[top++]=n--; t=y; y=z; z=t; } move(x,1,z); if(top) { n=stack[--top]; t=y; y=z; z=t; move(x,n,z); --n; t=x; x=y; y=t; } } if(n==1) move(x,1,z); }

void main() { int n=3; /*3层塔（可以修改！）*/ printf("hanoi puts:\n"); hanoi(n,'a','b','c');

getch(); c=0; printf("hanoi_w_w puts:\n"); hanoi_w_w(n,'a','b','c');

getch(); c=0; printf("hanoi_w_if puts:\n"); hanoi_w_if(n,'a','b','c'); printf("\n\n End! Remember STN_LCD!"); getch(); } 从上面的非递归化程序中可以看出：由于采用了”栈顶跟踪“技术，将原本要保存的4个参数，缩短为1个， 这样大大提高了非递归化程序的效率。下面看一个更复杂的例子：

例三：阿克曼函数的非递归化 阿克曼函数的定义为： [ n+1， m=0 akm(m,n)=| akm(m-1,1)， m!=0,n=0 [ akm(m-1,akm(m,n-1))， m!=0,n!=0

/*以下程序在TC2.0编译！*/ #include <stdio.h> #include <string.h>

/*递归形式的阿克曼函数：二层嵌套递归*/ int akm(int m,int n) { /*注意：调用时n不能为负！*/ if(m==0) return n+1; /*注意：akm函数用栈十分多！当参数m为4以上时，要耗尽tc所有的栈空间！！*/ else if(n==0) return akm(m-1,1); else return akm(m-1,akm(m,n-1)); }

/*以下函数是二层嵌套递归，采用while-while-while形式进行非递归化*/ /*注意：这个函数参考了严蔚敏的《数据结构题集》p189上的函数，但书上的算法保存了两个参数 我只保存了一个参数m，提高了效率*/ int akm_w_w(int m,int n) { /*注意：调用时n不能为负！*/ int s[5000]; /*栈中只保存参数m，参数n由”栈顶跟踪“决定*/ int top=0; while(m||top) { while(m) { while(n) {s[top++]=m; --n;} --m; n=1; } if(top) m=s[--top]-1,++n; } return n+1; }

/*用while-if-if形式改写*/ int akm_w_if(int m,int n) { int s[5000]; /*注意：akm函数用栈十分多！当参数m为4以上时，要耗尽tc所有栈空间！！*/ int top=0; while(m||top) { if(m) { if(n) s[top++]=m,--n; else --m,n=1; } else if(top) m=s[--top]-1,++n; } return n+1; }

main() { printf("\n akm:%d",akm(3,7)); /*不能调用akm(4,*)（及4以上），参数4（及以上）的akm 函数增长太快，系统栈将被耗尽！*/ printf("\n akm_w_w:%d",akm_w_w(3,7)); printf("\n akm_w_if:%d",akm_w_if(3,7)); printf("\n End! Remember STN_LCD!"); getch(); }

最后，介绍一种非常常用的非递归化方法：”标记栈法“（自创名词，如有不妥请更正）。 我们都知道二叉树的后序遍历非递归算法比较特殊：它不能采用先序或中序非递归算法一样形式的算法， 因为在后序遍历算法在执行过程中要两次访问某个结点才能确定遍历顺序，而普通的先序或中序非递归算法 用栈顶跟踪当前访问结点（栈顶是当前访问结点的祖先和父亲），不需要计数，但在后序遍历算法中 为了能确定访问结点的次数，必须对栈中结点的访问次数进行标记，从而要定义”标记栈“，所以我 称这种算法为”标记栈法“，应该不是很过分吧。

例四：二叉树的后序遍历非递归算法

/*以下程序在TC2.0编译！*/ /*程序默认的先序建树序列为：“abdg e c f ”*/ #include <stdio.h> #include <stdlib.h> #include <string.h> char tree[30]; /*tree数组为先序建树序列*/ int ti=0;

typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;

/*先序建树函数！*/ void CreateBiTree(BiTree *T) { char ch; ch=tree[ti++]; if(ch==NULL) return; if(ch==' ') *T=NULL; else { *T=(BiTree)malloc(sizeof(BiTNode)); (*T)->data=ch; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } }

/*二叉树的后序遍历递归算法*/ void PostOrder(BiTree T) { if(T) { PostOrder(T->lchild); PostOrder(T->rchild); printf("%c ",T->data); } }

/*采用”标记栈法“的后序遍历非递归算法（while-while形式）*/ void PostOrder_zb(BiTree t) { int tag[100],top=0; /*tag为标记栈*/ BiTree stack[100]; while(t||top) { while(t) { stack[++top]=t; tag[top]=0; /*标记栈置为0：第一次访问*/ t=t->lchild; } if(top) { if(tag[top]==1) {printf("%c ",stack[top]->data); --top;} /*如果这个结点访问了两次，输出之*/ else { t=stack[top]; /*否则置栈顶为：第二次访问*/ tag[top]=1; t=t->rchild; } } } }

/*采用”标记栈法“的后序遍历非递归算法（while-if形式）*/ void PostOrder_zb_if(BiTree t) { int tag[100],top=0; /*tag为标记栈*/ BiTree stack[100]; while(t||top) { if(t) { stack[++top]=t; tag[top]=0; /*标记栈置为0：第一次访问*/ t=t->lchild; } else { if(tag[top]==1) {printf("%c ",stack[top]->data); --top;} /*如果这个结点访问了两次，输出之*/ else { t=stack[top]; /*否则置栈顶为：第二次访问*/ tag[top]=1; t=t->rchild; } } } }

main() { BiTree T=NULL; strcpy(tree,"abdg e c f ");/*该树的先序序列为:abdgecf*/ CreateBiTree(&T); printf("\nPostOrder output:"); PostOrder(T); printf("\nPostOrder_zb output:"); PostOrder_zb(T); printf("\nPostOrder_zb_if output:"); PostOrder_zb_if(T); getch(); }

用”标记栈法“设计非递归程序时，有个非常重要的特点：非递归程序中的参数栈保存着从根结点到该结点的 完整路径！举个大家都熟悉的例子：huffman树编码函数中采用了case-case结构的”标记栈法“，在函数中每搜 索到一个叶子结点就输出编码，编码序列就保存在参数栈中；还有：求二叉树根结点到某个结点的路径时 用”标记栈法“搜索到该结点的时候，参数栈（不是标记栈）中就保存着根结点到这个结点的路径。 其实，上面的PostOrder_zb函数也可以实现树的先序和中序遍历，只需要修改printf的位置就可以了，可见该算 法功能的强大。”标记栈法“不仅可以用在树的操作上，如果你的水平很高，可以在许多的方面用到这种算法。 随便说一句：如果想考研的话，这种算法必须要掌握！有些名牌大学的研究生计算机基础知识考题要比”软件 设计师“考试试题有水平的多。 还有一种”类似菲波那契函数“的递归体结构：return fib(n-1)+fib(n-2);这种函数的非递归化比较简单： 用”栈迭代“就可以实现。有兴趣的同学不妨查一查资料。 本人接触编程的时间不到两年，所以对算法与程序根本谈不上精通，只是平时喜欢钻研一些算法。 以上的例子中可能包含一些错误或可笑的说法（比如什么栈顶跟踪或标记栈等），希望真正的高手给予指点！ 如有什么问题或建议请发送到dianzi8801@sina.com，我不喜欢上QQ。

好强啊！佩服

应该学学

厉害厉害