知识卡片
尾位置不保证尾调用优化
尾递归把递归调用放在当前函数最后需要执行的位置,常通过累加参数把结果提前带入下一层,返回后不再做合并工作。
这给实现复用调用空间的机会,但是否优化由语言和编译器决定。Go不保证尾调用优化,原书Go版tailRecur不能仅因写成尾形式就算常数栈空间;需要有界空间时,应明确改成循环并核对状态等价。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
如果函数在返回前的最后一步才进行递归调用 ,则该函数可以被编译器或解释器优化,使其在空 间效率上与迭代相当。这种情况被称为「尾递归tail recursion」 。 ‧ 普通递归 :当函数返回到上一层级的函数后,需要继续
参考来源
- 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[21432,21542))
- 结论依据:实际尾递归定义、累加求和和不支持优化提示,按Go版限定不虚称优化生效。
- 原始内容:如果函数在返回前的最后一步才进行递归调用 ,则该函数可以被编译器或解释器优化,使其在空 间效率上与迭代相当。这种情况被称为「尾递归tail recursion」 。 ‧ 普通递归 :当函数返回到上一层级的函数后,需要继续