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

Reference

可以点击这里看一个视频