知识卡片

普通读书笔记卡 · 5654.c.3.a.1

尾位置不保证尾调用优化

理解等级:中级

尾递归把递归调用放在当前函数最后需要执行的位置,常通过累加参数把结果提前带入下一层,返回后不再做合并工作。

这给实现复用调用空间的机会,但是否优化由语言和编译器决定。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」 。 ‧ 普通递归 :当函数返回到上一层级的函数后,需要继续