Recursion Tree

定义 Definition

recursion tree（递归树）：一种用树形结构来表示递归调用过程的方法，常用于分析递归算法的时间复杂度（例如把每一层的子问题规模与代价加总）。

发音 Pronunciation (IPA)

/rɪˈkɝːrʒən triː/

例句 Examples

A recursion tree can help you see how the work grows at each level.
递归树可以帮助你看清每一层的工作量是如何增长的。

Using a recursion tree, we sum the costs across all levels to estimate the running time of the divide-and-conquer algorithm.
使用递归树，我们把各层的代价相加，从而估算分治算法的运行时间。

词源 Etymology

recursion 来自拉丁语 recurrere（“跑回、返回”），在计算机领域指“函数/过程调用自身”的思想；tree 指“树状结构”。合起来的 recursion tree 就是“用树来展开并展示递归返回与分裂的结构”，尤其用于复杂度分析的可视化表达。

相关词 Related Words

• Recursion
• Recurrence
• Divide-and-Conquer
• Master Theorem
• Time Complexity
• Call Stack
• Dynamic Programming

文学与经典出处 Literary Works

• Introduction to Algorithms（CLRS，《算法导论》）：在分治递归式的分析中常用递归树法来估算总成本。
• The Algorithm Design Manual（Steven S. Skiena，《算法设计手册》）：讨论递归与分治策略时会用树形展开帮助理解复杂度。
• 计算机科学课程与讲义（如 MIT/Stanford 的算法课程讲义）：讲解递归式（recurrence）与复杂度时常配套使用 recursion tree 方法。