jyy在操作系统的课上讲的这些内容给我幼小的心灵带来了很大的冲击，使我对程序这种东西到底是什么有了更进一步的认识。
我以前一直觉得自己知道什么叫递归，甚至能手动写一些将递归转换为非递归的算法，但是这样做其实很大程度上是在学别人怎么做，为什么做，那我自己对递归、对程序的到底是如何理解的呢？所谓的调用到底是什么？从汇编的角度，我想这些问题会很清晰。
fibonacci数列示例:栈帧模拟
首先我们需要明确一点, 在使用栈模拟运行时栈时, 我们需要站在汇编语言的角度思考问题, 函数运行过程中产生的临时变量等不能再忽略掉, 需要明确为一条语句.就如下例中的变量t1, t2. 接下来我们看代码.
typedef struct Frame {
int pc, n, rv, t1, t2; //pc指示当前栈帧运行到了哪一步
} Frame; // 一个栈帧, 由于是递归调用, 栈帧的大小就是确定的.
#define call(...) ({ *(++top) = (Frame){.pc = 0, __VA_ARGS__}; })
#define goto(loc) ({ f->pc = (loc)-1; })
#define ret() ({ top--; })
int fibs(int n) {
Frame stk[64], *top = stk - 1;
int rax = 0; //模拟rax寄存器, 保存函数返回值
call(n);
for (Frame *f; (f = top) >= stk; f->pc++) {
//在switch中, 每一个case相当于对应的递归函数中的一行.
//但需要注意的是, 临时变量需要显式的表示出来.
switch (f->pc) {
case 0:
if (f->n == 1 || f->n == 2) {
f->rv = 1;
goto(5);
}
break;
case 1:
call(f->n - 1);
break;
case 2:
f->t1 = rax;
break;
case 3:
call(f->n - 2);
break;
case 4:
f->t2 = rax;
break;
case 5:
if (f->rv == 0) f->rv = f->t1 + f->t2;
rax = f->rv;
ret();
//由于在递归函数中有两种返回方式, 所以这里需要判断一下是哪一种
break;
}
}
return rax;
}