函数调用与运行栈

复习

变量、类型与表达式：名字如何代表数据，表达式如何变成运算
分支与循环：高级语言结构如何落到比较和跳转指令
函数：把一段工作命名、传入参数并获得结果

TL;DR

用栈保存返回地址、参数和局部变量
栈是后进先出：后压进去的先弹出来
调用时压栈，返回时弹出，PC 就能准确回到调用处
递归是同一函数的多层调用，栈天然能记录每一层

正文

　　上一章留下两个问题：函数怎么知道该跳回哪儿？参数和局部变量又放在哪？这一章用一个东西把两件事一起解决—— 栈。

一摞盘子

　　栈（stack）听起来高级，其实就是“一摞盘子”：

只能从顶上放，也只能从顶上取
后放上去的，先被取下来

　　这种“后进先出”的规矩，叫 LIFO（Last In, First Out）。我们给机器留出一段存储当栈，再用一个 栈指针 （SP，Stack Pointer）记住“现在摞到哪了”。

高地址   ┌───────────┐
        │    ...    │
        ├───────────┤
        │  最近放入  │ ← SP 指向栈顶
        └───────────┘
低地址

调用时压栈

　　现在看函数调用是怎么一回事。机器可以配备两条指令：

CALL 目标：先把“下一条指令的地址”（也就是返回地址）压进栈，再跳到目标
RET：从栈顶弹出返回地址，跳回那里

　　回到上一章的谜题：max 被三个地方调用，它怎么知道回哪儿？答案就在栈里—— 每次调用都把这次的返回地址压在栈顶 。返回时弹出的是哪一个，就跳回哪一个，不会串。

调用 max 前        调用 max 后
┌──────────┐      ┌──────────┐
│    ...   │      │    ...   │
├──────────┤      ├──────────┤
│          │      │ 返回地址  │ ← SP
└──────────┘      └──────────┘

局部数据也放栈上

　　光记返回地址还不够。参数 a、b，函数里的局部变量，也需要地方放。而寄存器就那么几个，函数一嵌套就不够用了。

　　于是约定：调用的同时，把参数也压进栈；函数内部再在栈上留出一块空间放局部变量。一次调用对应的这一小摞数据，就叫一个栈帧（stack frame）。RET 之前，把这摞数据一收，栈就回到调用前的样子。

　　一次调用大致是这样：

把参数压栈
CALL 把返回地址压栈，跳到函数
函数在栈上分配空间给局部变量，开始干活
把返回值放到约定的地方
撤销本次的栈帧，RET 弹出返回地址，跳回调用处

一层套一层

　　函数里再调用函数，栈也不怕。假设 A 调用 B，B 又调用 C：

        ┌──────────┐
        │  A 的栈帧 │
        ├──────────┤
        │  B 的栈帧 │
        ├──────────┤
        │  C 的栈帧 │ ← SP
        └──────────┘

　　C 先返回，它的栈帧被收走；然后是 B，再是 A。 后进去的先出来 ——和那摞盘子一模一样。

递归

　　有了栈，一个特别漂亮的用法就出现了：函数调用它自己，叫递归（recursion）。

function fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

　　求 fact(3) 时，它会去调 fact(2)，fact(2) 再调 fact(1)……每一层调用都往栈上压一个自己的栈帧，各自记着“我的 n 是几”“算完该回到哪里”。等到 fact(0) 返回 1，再一层层往上乘回去。

　　每层的数据互不干扰，靠的就是“每层一个栈帧”。栈把“一层层嵌套”这件事，安排得井井有条。

　　当然，栈也不是无限的。如果递归太深，栈帧摞得太高，超出预留的栈空间，就会 栈溢出 （stack overflow）——这也是初学递归时最容易撞上的坑。

　　到这里，函数、参数、返回、递归，全都讲通了。可我们一直没问：代码放哪里、数据放哪里、栈又放在内存的哪一段？下一章，我们把程序在内存里的全貌铺开来看。

思考题

　　递归求 fact(3) 的过程中，栈上会依次出现哪几层？每层各自记住什么？如果忘了设置“n == 0 就返回”这个条件，栈会发生什么？

小结

知识点

栈：后进先出的一段存储，用 SP 指向栈顶
CALL 压入返回地址并跳转，RET 弹出返回地址并返回
栈帧：一次调用对应的参数、局部变量和返回地址
嵌套调用与递归都靠栈记录每一层
栈溢出：调用太深，超出栈空间

参考资料

Wikipedia(zh)：调用栈：函数调用的栈
Wikipedia(zh)：栈 (数据结构)：后进先出
Wikipedia(zh)：递归：函数调用自身

设计师 | 南国微雪

微雪博客