30、数据结构与算法Python:递归小结

整理递归的基本条件、重复计算与记忆化概念,说明动态规划还需要识别子问题结构。

简明结论

递归需要可到达的结束条件,并让每一步向该条件推进。它适合表达某些自相似问题,也可能造成重复计算或较深调用栈。

递归需要可到达的结束条件,并让每一步向该条件推进。它适合表达某些自相似问题,也可能造成重复计算或较深调用栈。

记忆化可缓存重复子问题;是否适合动态规划,还应识别状态、转移和子问题之间的关系,不能只凭“有最优子结构”就当作完成算法设计。本页是概念小结,没有实现或性能比较。