知识卡片

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

递归需要收缩与基本情况

理解等级:中级

递归把原问题交给形式相同而规模更小的子问题,再利用子问题结果完成当前问题。终止条件给出已知的基本情况,递归调用负责收缩,返回阶段负责合并。

只写函数调用自身不保证终止。原书求和及斐波那契例要求n至少为1;若输入0或负数而只检查n==1,可能一直向负方向递归。边界定义必须与收缩方向配合。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低 。 第2 章 复杂度分析 hello‑algo.com 24 如图2‑4 所示,在触发终止条件前,同时存在 个未返回的递归函数,递归深度为 。 图2‑4 递

    参考来源

    - 位置:《Hello 算法--Go版本》第02章《复杂度分析》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[21265,21375)) - 结论依据:前单元递归三要素与本单元调用栈/求和例共同支持,主引文选实际栈说明,边界来自实际代码。 - 原始内容:递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低 。 第2 章 复杂度分析 hello‑algo.com 24 如图2‑4 所示,在触发终止条件前,同时存在 个未返回的递归函数,递归深度为 。 图2‑4 递