知识卡片
尾递归把回归工作前移
尾递归的递归调用在该执行路径上直接决定返回结果,返回后不再需要把结果与当前状态组合。普通fact的n×fact(n−1)仍有乘法待做;facttail把累计乘积放入a,直接return facttail(n−1,n*a)。
原例从(4,1)到(3,4)、(2,12)、(1,24),最终返回24。a保存累计乘积,不是正文误称的“递归深度”;每一步把下一层需要的状态显式传下去。
代码对n返回0,对n=0返回1,对n=1返回a;因此公式在n=0写返回a与代码并不对所有a一致,常规求n!需按说明从a=1开始。它仍未处理int溢出,也不能仅因改写形式就宣称已测得空间下降。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。 当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事
参考来源
- 位置:《算法精解:C语言描述》第3章《尾递归》(spine1195;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1163.html;u036-ch03-004)。
- 结论依据:36全文与02681-02684公式、(4,1)链、完整facttail及单帧图;逐项对照发现a不是深度、n0公式与代码差别,按实际输入限定。
- 原始内容:在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码。 当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的。编译器可以做到这点,因为递归调用是当前活跃期内最后一条待执行的语句,于是当这个调用返回时栈帧中并没有其他事