Recurrence Relation

释义 Definition

递推关系式 / 递归关系：用来把一个序列或函数在较小参数处的值与较大参数处的值联系起来的等式，常用于描述算法时间复杂度、数列定义与动态规划等。（也常简称为 recurrence 或 recurrence equation。）

发音 Pronunciation (IPA)

/rɪˈkʌrəns rɪˈleɪʃən/

例句 Examples

A recurrence relation defines each term using earlier terms.
递推关系式用更早的项来定义序列的每一项。

Using the recurrence relation (T(n)=2T(n/2)+n), we can apply the Master Theorem to show (T(n)=\Theta(n\log n)).
利用递推关系 (T(n)=2T(n/2)+n)，我们可以用主定理推出 (T(n)=\Theta(n\log n))。

词源 Etymology

recurrence 来自拉丁语 recurrere（“跑回、再次发生”），表示“反复出现/回到先前”。relation 源自拉丁语 relatio（“联系、关联”）。合起来 recurrence relation 字面意思就是“把当前情况与先前情况联系起来的关系式”，强调“用已知的前面结果来推出后面结果”。

相关词 Related Words

• Recurrence
• Recursion
• Recursive
• Sequence
• Iteration
• Closed Form
• Master Theorem
• Dynamic Programming

文学与经典著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）：用递推关系刻画分治算法的运行时间。
• Concrete Mathematics（Graham, Knuth, Patashnik，《具体数学》）：大量讨论由递推关系定义的数列与求解技巧。
• The Art of Computer Programming（Donald E. Knuth，《计算机程序设计艺术》）：在组合数学与算法分析中频繁使用递推关系。
• Generatingfunctionology（Herbert S. Wilf）：将递推关系与生成函数联系起来用于求解与分析序列。