DEV Community
·
递归（数据结构与算法 - 9）
💡
原文英文，约1600词，阅读约需6分钟。
📝
内容提要
递归是编程中的基本概念，指函数自我调用直到满足基准条件。其时间复杂度因问题而异，如斐波那契数列的复杂度较高。优化方法包括记忆化、动态规划等，可避免栈溢出并提高效率。
🎯
关键要点
-
递归是编程中的基本概念，指函数自我调用直到满足基准条件。
-
基准条件是递归函数的重要部分，定义了函数停止自我调用的情形。
-
递归的时间复杂度因问题而异，简单的斐波那契数列具有指数时间复杂度。
-
通过记忆化等优化技术，可以将递归算法的时间复杂度降低到多项式时间。
-
二分查找是一个具有对数时间复杂度的算法。
-
深度优先搜索（DFS）在图中的时间复杂度为线性。
-
递归并不总是指数级的，时间复杂度取决于问题和实现方式。
-
递归可能导致栈溢出或段错误，需妥善管理递归深度。
-
动态规划适用于某些问题，尤其是涉及计数或寻找最佳解的情况。
-
优化递归问题的方法包括记忆化、动态规划、空间优化和分治法等。
-
分治法将问题分解为子问题，递归解决每个子问题并合并结果。
➡️
