知识卡片
显式栈可以模拟递归
把递归尚未处理的状态保存到显式栈,再按后进先出的顺序取出处理,可以模拟调用栈的进入和返回。原书先把n到1压栈,再逐个弹出累加,保留了先递后归的顺序。
这种改写只是把上下文搬到数据结构,不自动减少空间。求和可以另用一个累加器达到常数辅助空间,但那是利用问题性质的进一步简化;复杂递归改写也可能降低可读性。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
我们可以使用一个显式的栈来模拟调用栈的行为 ,从而将递归转化为迭代形式: // === File: recursion.go === /* 使用迭代模拟递归 */ func forLoopRecur(n int) int
参考来源
- 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[23364,23474))
- 结论依据:原文具体PushBack/Back/Remove流程与转换代价解释,避免把递归改循环等同降空间。
- 原始内容:我们可以使用一个显式的栈来模拟调用栈的行为 ,从而将递归转化为迭代形式: // === File: recursion.go === /* 使用迭代模拟递归 */ func forLoopRecur(n int) int