「栈」栈在递归转非递归中的应用
为什么要学习递归与非递归的转换的实现方法?
- 并不是每一门语言都支持递归的.
- 在SD，省选的老年机栈空间十分小
非递归毒瘤
递归与非递归转换的原理
递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.
稍有常识的人都知道，学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非
递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的二叉树说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了.
Step 1 - Easy
先序遍历
递归
void preorder (root) :
if root not NULL :
visit root
preorder left child
preorder right child 非递归
void preorder (Node *root) :
init stack S
push root
while Stack S not empty
while S.get_top(p) && p
visit p
push leftchild
pop p in S
if Stack S not empty :
pop p in S
push right child in S 中序遍历
递归
（略）
非递归
void inorder(Bitree T) {
initstack(S);
push(S, T);
while (!stackempty(S)) {
while (gettop(S, p) && p) push(S, p->;lchild);
pop(S, p);
if (!stackempty(S)) {
pop(S, p);
visit(p);
push(S, p->;rchild);
}
}
} 后序遍历
这个就有一些难度了
递归
(略)
非递归
typedef struct Node{
BTNode* ptr;
enum {0,1,2} mark;
};
void postorder_nonrecursive(BiTree T) {
Node *a;
initstack(S);
push (S,{T,0});
while(!stackempty(S)) {
pop(S,a);
switch(a.mark) {
case 0:
push(S,{a.ptr,1});
if(a.ptr->;lchild) push(S,{a.ptr->;lchild,0});
break;
case 1:
push(S,{a.ptr,2});
if(a.ptr->;rchild) push(S,{a.ptr->;rchild,0});
break;
case 2:
visit(a.ptr);
}
}
} Step 2 - Normal
如何实现递归与非递归的转换
通常,一个函数在调用另一个函数之前,要作如下的事情:
- 将实在参数,返回地址等信息传递给被调用函数保存;
- 为被调用函数的局部变量分配存储区;
- 将控制转移到被调函数的入口.
从被调用函数返回调用函数之前,也要做三件事情:a
- 保存被调函数的计算结果;
- 释放被调函数的数据区;
- 依照被调函数保存的返回地址将控制转移到调用函数.
所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的.
ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现同步.
下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以得到:
- 访问当前结点:对目前的数据进行一些处理;
- 访问左子树:变换当前的数据以进行下一次处理;
- 访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式).
void preorder (root) :
if root not NULL :
visit root
preorder left child
preorder right child visit root这个操作就是对当前数据进行的处理, preorder left child就是把当前数据变换为它的左子树,访问右子树的操作可以同样理解了. 现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:
- 确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结构;
- 确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用树的"左子树"和"右子树"
- 确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的"叶子结点".
三个代表
好了上面的理论知识已经足够了,下面让我们看看几个例子,结合例子加深我们对问题的认识.即使上面的理论你没有完全明白,不要气馁,对事物的认识总是曲折的,多看多想你一定可以民白 (事实上我也是花了两个星期的时间才弄得比较明白得).
1. 毒瘤的f函数
int f (int n) {
int u1, u2, f;
if (n < 2) f = n + 1;
else {
u1 = f ((int) n / 2);
u2 = f ((int) n / 4);
f = u1 * u2；
}
return f;
} 下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点，我们看到当时
,这就是返回的语句,有人问为什么不是
,这也是一个返回的语句呀?
答案是:这条语句是在和
之后执行的,是这两条语句的父结点. 其次,什么是当前结点,由上面的分析,
即是父结点.然后,顺理成章的
和
就分别是左子树和右子树了.最后,我们可以看到,这个递归函数可以表示成后序遍历的二叉调用树.好了,树的情况分析到这里,下面来分析一下栈的情况,看看我们要把什么数据保存在栈中,在上面给出的后序遍历的如果这个过程你没非递归程序中我们已经看到了要加入一个标志域,因此在栈中要保存这个标志域;另外,
,
和每次调用递归函数时的
和
参数都要保存,这样就要分别有三个栈分别保存:标志域,返回量和参数,不过我们可以做一个优化,因为在向上一层返回的时候,参数已经没有用了,而返回量也只有在向上返回时才用到,因此可以把这两个栈合为一个栈.如果对于上面的分析你没有明白,建议你根据这个递归函数写出它的递归栈的变化情况以加深理解,再次重申一点:前期对树结构和栈的分析是最重要的,如果你的程序出错,那么请返回到这一步来再次分析,最好把递归调用树和栈的变化情况都画出来,并且结合一些简单的参数来人工分析你的算法到底出错在哪里.
ok,下面给出我花了两天功夫想出来的非递归程序
int f_nonrecursive(int n) {
int stack[20], flag[20], cp;
cp = 0;
stack[0] = n;
flag[0] = 0;
while (cp >;= 0) {
switch(flag[cp]) {
case 0:
if (stack[cp] >;= 2) {
flag[cp] = 1;
cp++;
stack[cp] = (int)(stack[cp - 1] / 2);
flag[cp] = 0;
} else {
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 1:
if (stack[cp] >;= 2) {
flag[cp] = 2;
cp += 2;
stack[cp] = (int)(stack[cp - 2] / 4);
flag[cp] = 1;
} else {
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 2:
if (flag[cp - 1] == 2) {
stack[cp - 2] = stack[cp] * stack[cp - 1];
flag[cp - 2] = 2;
cp = cp - 2;
} else
cp--;
break;
}
}
return stack[0];
} 算法分析:
- flag只有三个可能值: 0表示第一次访问该结点, 1表示访问的是左子树, 2表示已经结束了对某一棵子树的访问,可能当前结点是这棵子树的右子树,也可能是叶子结点.
- 每遍历到某个结点的时候,如果这个结点满足叶子结点的条件,那么把它的flag域设为2;否则根据访问的是根结点,左子树或是右子树来设置flag域,以便决定下一次访问该节点时的程序转向.
2. 毒瘤的快排
void QuickSort(int arr[], int left, int right) {
int i = left;
int j = right;
int temp = 0;
int mid = arr[(i + j) / 2]; //取数组中间的值作为“基准值”
while (i <= j) {
while (arr[i] < mid) i++;
while (arr[j] > mid) j--;
//小于基准值移至左边，大于基准值的移至右边
if (i <= j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
}
if (j > left) QuickSort(arr, left, j); //递归左半数组
if (i < right) QuickSort(arr, i, right); //递归右半数组
} 程序
void qsort_nonrecursive(int array[], int low, int high) {
int m[50], n[50], cp, p;
cp = 0; m[0] = low; n[0] = high;
while (m[cp] < n[cp]) {
while (m[cp] < n[cp]) {
p = partition(array, m[cp], n[cp]);
cp++;
m[cp] = m[cp - 1];
n[cp] = p - 1;
}
m[cp + 1] = n[cp] + 2;
n[cp + 1] = n[cp - 1];
cp++;
}
} 3. 毒瘤的阿克曼函数
int akm_recursive(int m, int n) {
int temp;
if (m == 0) return (n + 1);
else if (n == 0) return akm_recursive(m - 1, 1);
else {
temp = akm_recursive(m, n - 1);
return akm_recursive(m - 1, temp);
}
} 这道题目就当课后习题来说吧
(未完待续)