这篇文章上次修改于 613 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
手工栈，就是一种利用栈控制任务进程，实现消除递归的技术。
为什么要用栈呢？因为在函数的递归调用时，后调用的先计算，和栈的后进先出的规则很像。
把递归代码改成手工栈可以按照下面的方法
1. 把代码分成几部分：预处理、计算、规约。举个例子：
int fibb(int n) {
/* 预处理 */
if(n < 0) return -1;
/* 计算 */
if(n < 2) return 1;
int a = fibb(n-2);
int b = fibb(n-1);
/* 规约 */
return a+b;
}2. 设计指令：计算指令（带参数）、规约指令、跳出指令。比如在上面的斐波那契数列里，计算指令就是计算 fibb(n)，规约指令就是把两次递归得到的结果进行相加合并，跳出指令就是在所有运算完成之后，回到最外层并返回结果。
3. 使用两个栈：指令栈和结果栈。指令栈储存要计算的指令，结果栈储存计算过的结果。
4. 用一个无限循环代替原先代码的计算、递归调用、规约部分。
在预处理部分后，把跳出指令和第一个计算指令依次入栈。
在循环中，每次从指令栈顶部取出要执行的下一条指令。
在计算指令里，根据计算指令带的参数选择直接把结果push到结果栈里，或者进行递归调用。
在规约指令里，从结果栈的顶部pop出若干个结果，并把根据栈顶的这些结果得到新的结果，放回结果栈顶。
在跳出指令里，直接中断循环，把结果栈顶的第一个结果返回。
所以更改完成的斐波那契数列就是这样的：
int fibb_st(int n){
/* 预处理 */
if(n < 0) return -1;
stack<int> cs/*指令栈*/, ds/*结果栈*/;
cs.push(-1);
cs.push(n);
/* 主循环 */
while(true){
n = cs.top(); cs.pop();
/* 计算 */
if(n == 1 || n == 0){
ds.push(1);
} else if(n > 1){
cs.push(-2);
cs.push(n-1); cs.push(n-2);
/* 规约 */
} else if(n == -2){
int a = ds.top(); ds.pop();
int b = ds.top(); ds.pop();
ds.push(a+b);
/* 跳出 */
} else if(n == -1){
break;
/* 异常 */
} else return -1;
}
return ds.top();
}这里用了非负数表示计算指令，负数表示其他指令。
附赠：
强行非递归的快速排序：
typedef struct {
int l, h;
int kind;
} _qs_p;
void qsort_st(int a[], int low, int high) {
stack<_qs_p> cs;
_qs_p f = {0, 0, -1};
cs.push(f);
f.l = low;
f.h = high;
f.kind = 0;
cs.push(f);
while(true) {
_qs_p ins = cs.top();
cs.pop();
low = ins.l;
high = ins.h;
if(ins.kind == 0) {
if(low >= high) {
_qs_p n = {0, 0, 1};
cs.push(n);
continue;
}
int first = low, last = high;
int key = a[first];
while(first < last) {
while(first < last && a[last] >= key) last--;
a[first] = a[last];
while(first < last && a[first] <= key) first++;
a[last] = a[first];
}
a[first] = key;
_qs_p pp = {0, 0, 0};
pp.l = low;
pp.h = first - 1;
cs.push(pp);
pp.l = first + 1;
pp.h = high;
cs.push(pp);
} else if(ins.kind == 1) {
continue;
} else if(ins.kind == -1) {
break;
}
}
}（可读性： -∞ ）
最后说一句，这种方法有这么几个缺点：
- 得到的代码效率比较差，而且基本不能看。
- 不能用于循环中嵌套递归的情况。（当然你可以把循环改成尾递归，然后再改写，不过没人会闲到这么做的。）
没有评论