从递归到非递归

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;
}

reference

可以点击这里看一个视频