知识卡片
递归深度决定未返回上下文
普通递归向下调用时,尚未完成的层级保留局部状态和继续位置;最深层返回后再逐层恢复。因此栈空间要看同时未返回的深度,而不是只数最终结果数量。
循环中逐次调用并完成的函数不会把所有栈帧同时保留;递归链却可能。具体编译器可以内联或优化,调用成本并非固定常数,递归也不必在所有任务上都比迭代慢。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
函数的上下文数据都存储在称为“栈帧空间”的内存区域中,直至函数返回后才会被释放。因此, 递归 通常比迭代更加耗费内存空间 。 ‧ 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低 。 第2 章 复杂度分析
参考来源
- 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[21200,21309))
- 结论依据:原文栈帧、深度及对照图解释同时存活上下文,限定性能断言。
- 原始内容:函数的上下文数据都存储在称为“栈帧空间”的内存区域中,直至函数返回后才会被释放。因此, 递归 通常比迭代更加耗费内存空间 。 ‧ 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低 。 第2 章 复杂度分析