知识卡片

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

尾调用形式不保证消除

理解等级:中级

尾调用没有后续组合工作,因而可能被编译器改写成跳转或迭代式控制,减少逐层保留调用记录的需要。这是优化机会,不是写出尾递归就自动得到常数栈空间的语言承诺。

原书单帧图表示完成消除后的模型。是否实际发生取决于编译器、目标和选项等条件,不能把图当本轮编译结果。已核对GCC优化选项文档把兄弟/尾递归调用优化列为明确优化选项;未编译或检查本例机器码。

38把尾递归消除定义为以等价迭代控制替换最终尾递归调用;目的是减少额外调用开销,而非改变数学输出。等价仍须满足真实语言的求值及数值语义,不能仅因形式相似就跳过验证。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。

    • · 查看原书依据

      替换为等同的迭代控制结构,这不会改变函数的输出结果但能够避免一次额外的函数调用开销。在编译器设计中尾递归消除是一个重要的基本法则。 递归树 画图表能帮助我们形象地理解递归函数的调用顺序。递归树在形式上有所不同,展示递归计算阶乘的图3-1和图3-4与表示确定整数质因子的图3-6都是递归树。递归树最常用

    参考来源

    - 位置:《算法精解:C语言描述》第3章《尾递归》(spine1195;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1163.html;u036-ch03-005)。 - 结论依据:36正文的覆盖栈帧说明与02684单帧图展示优化意图;GCC官方选项说明用于限定自动/必然优化的过强表述,而不生成本机性能数据。 - 原始内容:覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事情可做,因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个,这样所使用的栈空间就大大缩减了,这使得实际的运行效率会变得更高。 - 位置:《算法精解:C语言描述》第3章《相关主题》(spine1197;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1165.html;u038-ch03-005)。 - 结论依据:38把尾递归消除定义为以等价迭代控制替换最终尾递归调用;目的是减少额外调用开销,而非改变数学输出。等价仍须满足真实语言的求值及数值语义,不能仅因形式相似就跳过验证。 - 原始内容:替换为等同的迭代控制结构,这不会改变函数的输出结果但能够避免一次额外的函数调用开销。在编译器设计中尾递归消除是一个重要的基本法则。 递归树 画图表能帮助我们形象地理解递归函数的调用顺序。递归树在形式上有所不同,展示递归计算阶乘的图3-1和图3-4与表示确定整数质因子的图3-6都是递归树。递归树最常用