知识卡片
活跃调用保留返回所需状态
活跃记录保存一次尚未结束调用所需的信息,例如参数、临时值与返回后继续执行的状态。普通阶乘在返回子调用结果后还要乘当前n,因此当前调用不能只留下子调用而忘掉这项工作。
02680的图把fact(4)、fact(3)、fact(2)、fact(1)依次压入,再按相反顺序返回:
| 当前返回层 | 组合结果 |
|---|---|
| fact(1) | 1 |
| fact(2) | 2×1=2 |
| fact(3) | 3×2=6 |
| fact(4) | 4×6=24 |
这种后进先出关系解释栈为何适合调用/返回。保存和恢复状态有时间及空间成本,递归深度大时尤其要注意;图中的五个分区是教学模型,不是所有ABI与优化后代码必须逐项具备的物理布局。
37说明未终止递归在持续建立新调用帧时可能耗尽栈,但不能保证所有实现都用相同方式检测或一定按同一错误终止。若尾调用确实已消除,也不再按“每次调用加帧”推断溢出。原文帧指针/栈指针段有排印混乱,二者职责与优化须以具体ABI判断,不生成普遍物理寄存器规则。
78以f1→f2→f3及逆序返回再次说明活跃记录后进先出;这是程序栈的常见模型,优化后的调用未必逐次建立独立物理帧,不能把模型推广为全部实现布局。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 活跃调用保留返回所需状态
- · 问与答
- · 第6章 栈和队列
原书出处 · 3 处
- · 查看原书依据
栈帧由5个区域组成:输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数(见图3-2b)。输入参数是传递到活跃记录中的参数;输出参数是传递给在活跃记录中调用的函数所使用的。一个活跃记录中的输出参数就成为栈中下一个活跃记录的输入参数。函数调用产生的活跃记录将一直存
- · 查看原书依据
栈的增长会超过可接受的值,程序会因为栈溢出而终止运行。当程序执行时,一个称为帧指针的特殊指针会寻址栈顶的帧。正是栈指针指向实际的栈顶(即,下一个栈帧将被压入的位置。因此,虽然某个系统可能使用来判断栈溢出,但是它可能是通常会使用的栈指针。) 问:递归函数常常能够以简洁而精确的方式描述计算问题。请描述下
- · 查看原书依据
f1调用f2,f2调用f3,每次当函数调用发生时,程序就会分配空间来记录此激活信息。这些记录会一直存在直到相应的函数返回。因为函数调用与函数返回是一个相反的过程,所以活跃记录的获取与释放也与其存储空间分配的顺序是相反的。用于检索数据的另一种常用结构称为队列,它是按照元素到达的先后顺序来释放元素的。例