知识卡片

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

显式栈可以模拟递归

理解等级:中级

把递归尚未处理的状态保存到显式栈,再按后进先出的顺序取出处理,可以模拟调用栈的进入和返回。原书先把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