知识卡片

普通读书笔记卡 · 5654.c.3.h.1 · 生成模型:未记录

活跃调用保留返回所需状态

理解等级:中级

活跃记录保存一次尚未结束调用所需的信息,例如参数、临时值与返回后继续执行的状态。普通阶乘在返回子调用结果后还要乘当前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 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 3 处

    • · 查看原书依据

      栈帧由5个区域组成:输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数(见图3-2b)。输入参数是传递到活跃记录中的参数;输出参数是传递给在活跃记录中调用的函数所使用的。一个活跃记录中的输出参数就成为栈中下一个活跃记录的输入参数。函数调用产生的活跃记录将一直存

    • · 查看原书依据

      栈的增长会超过可接受的值,程序会因为栈溢出而终止运行。当程序执行时,一个称为帧指针的特殊指针会寻址栈顶的帧。正是栈指针指向实际的栈顶(即,下一个栈帧将被压入的位置。因此,虽然某个系统可能使用来判断栈溢出,但是它可能是通常会使用的栈指针。) 问:递归函数常常能够以简洁而精确的方式描述计算问题。请描述下

    • · 查看原书依据

      f1调用f2,f2调用f3,每次当函数调用发生时,程序就会分配空间来记录此激活信息。这些记录会一直存在直到相应的函数返回。因为函数调用与函数返回是一个相反的过程,所以活跃记录的获取与释放也与其存储空间分配的顺序是相反的。用于检索数据的另一种常用结构称为队列,它是按照元素到达的先后顺序来释放元素的。例

    参考来源

    - 位置:《算法精解:C语言描述》第3章《基本递归》(spine1194;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1162.html;u035-ch03-002)。 - 结论依据:35活跃记录段全文与02679-02680两图:五区模型、参数4/3/2/1和七步压入/返回已逐幅实读,表为原图数值的重新组织。 - 原始内容:栈帧由5个区域组成:输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数(见图3-2b)。输入参数是传递到活跃记录中的参数;输出参数是传递给在活跃记录中调用的函数所使用的。一个活跃记录中的输出参数就成为栈中下一个活跃记录的输入参数。函数调用产生的活跃记录将一直存 - 位置:《算法精解:C语言描述》第3章《问与答》(spine1196;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1164.html;u037-ch03-002)。 - 结论依据:37说明未终止递归在持续建立新调用帧时可能耗尽栈,但不能保证所有实现都用相同方式检测或一定按同一错误终止。若尾调用确实已消除,也不再按“每次调用加帧”推断溢出。原文帧指针/栈指针段有排印混乱,二者职责与优化须以具体ABI判断,不生成普遍物理寄存器规则。 - 原始内容:栈的增长会超过可接受的值,程序会因为栈溢出而终止运行。当程序执行时,一个称为帧指针的特殊指针会寻址栈顶的帧。正是栈指针指向实际的栈顶(即,下一个栈帧将被压入的位置。因此,虽然某个系统可能使用来判断栈溢出,但是它可能是通常会使用的栈指针。) 问:递归函数常常能够以简洁而精确的方式描述计算问题。请描述下 - 位置:《算法精解:C语言描述》第6章《第6章 栈和队列》(spine1231;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1198.html;u078-ch03-002)。 - 结论依据:78以f1→f2→f3及逆序返回再次说明活跃记录后进先出;这是程序栈的常见模型,优化后的调用未必逐次建立独立物理帧,不能把模型推广为全部实现布局。 - 原始内容:f1调用f2,f2调用f3,每次当函数调用发生时,程序就会分配空间来记录此激活信息。这些记录会一直存在直到相应的函数返回。因为函数调用与函数返回是一个相反的过程,所以活跃记录的获取与释放也与其存储空间分配的顺序是相反的。用于检索数据的另一种常用结构称为队列,它是按照元素到达的先后顺序来释放元素的。例