递归 (计算机科学)

在计算机科学中，递归是一种解决计算问题的方法，其中的解决方案取决于同一问题的较小实例的解决方案。 递归通过使用从自己的代码中调用自己的函数来解决此类递归问题。 该方法可以应用于多种类型的问题，递归是计算机科学的核心思想之一。

递归的力量显然在于可以通过有限的语句定义无限的对象集。 同样，有限递归程序可以描述无限次的计算，即使该程序不包含明确的重复。

—>Niklaus Wirth，算法 + 数据结构 = 程序，1976

大多数计算机编程语言通过允许函数从其自己的代码中调用自身来支持递归。 一些函数式编程语言（例如，Clojure）没有定义任何循环结构，而是仅依靠递归来重复调用代码。 可计算性理论证明，这些只递归的语言是图灵完备的； 这意味着它们与基于 while 和 for 等控制结构的命令式语言一样强大（它们可用于解决相同的问题）。

从自身内部重复调用一个函数可能会导致调用堆栈的大小等于所有涉及的调用的输入大小的总和。 由此可见，对于可以通过迭代轻松解决的问题，递归通常效率较低，对于大型问题，使用尾调用优化等优化技术是基础。

一种常见的算法设计策略是将问题划分为与原始问题类型相同的子问题，解决这些子问题，然后组合结果。 这通常被称为分而治之的方法； 当与存储先前解决的子问题的结果的查找表结合使用时（以避免重复解决它们并产生额外的计算时间），它可以称为动态规划或记忆。

许多计算机程序必须处理或生成任意数量的数据。 递归是一种表示程序员不知道确切大小的数据的技术：程序员可以使用自引用定义来指定此数据。 有两种类型的自指定义：归纳定义和共归纳定义。

归纳定义的递归数据定义是指定如何构造数据实例的定义。 例如，可以归纳地定义链表（这里使用 Haskell 语法）：

数据 ListOfStrings = EmptyList | 缺点 String ListOfStrings

上面的代码指定一个字符串列表为空，或者指定一个包含一个字符串和一个字符串列表的结构。 定义中的自引用允许构造任意（有限）数量的字符串列表。

归纳定义的另一个例子是自然数（或正整数）：

自然数是 1 或 n+1，其中 n 是自然数。

类似地，递归定义通常用于对编程语言中的表达式和语句的结构建模。