知识卡片

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

递归深度决定未返回上下文

理解等级:中级

普通递归向下调用时,尚未完成的层级保留局部状态和继续位置;最深层返回后再逐层恢复。因此栈空间要看同时未返回的深度,而不是只数最终结果数量。

循环中逐次调用并完成的函数不会把所有栈帧同时保留;递归链却可能。具体编译器可以内联或优化,调用成本并非固定常数,递归也不必在所有任务上都比迭代慢。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      函数的上下文数据都存储在称为“栈帧空间”的内存区域中,直至函数返回后才会被释放。因此, 递归 通常比迭代更加耗费内存空间 。 ‧ 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低 。 第2 章 复杂度分析

    参考来源

    - 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[21200,21309)) - 结论依据:原文栈帧、深度及对照图解释同时存活上下文,限定性能断言。 - 原始内容:函数的上下文数据都存储在称为“栈帧空间”的内存区域中,直至函数返回后才会被释放。因此, 递归 通常比迭代更加耗费内存空间 。 ‧ 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低 。 第2 章 复杂度分析