知识卡片
尾调用形式不保证消除
尾调用没有后续组合工作,因而可能被编译器改写成跳转或迭代式控制,减少逐层保留调用记录的需要。这是优化机会,不是写出尾递归就自动得到常数栈空间的语言承诺。
原书单帧图表示完成消除后的模型。是否实际发生取决于编译器、目标和选项等条件,不能把图当本轮编译结果。已核对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都是递归树。递归树最常用