在计算机科学中，递归是一种解决计算问题的方法，其中的解决方案取决于同一问题的较小实例的解决方案。 递归通过使用从自己的代码中调用自己的函数来解决此类递归问题。 该方法可以应用于多种类型的问题，递归是计算机科学的核心思想之一。
递归的力量显然在于可以通过有限的语句定义无限的对象集。 同样，有限递归程序可以描述无限次的计算，即使该程序不包含明确的重复。
—>Niklaus Wirth，算法 + 数据结构 = 程序，1976
大多数计算机编程语言通过允许函数从其自己的代码中调用自身来支持递归。 一些函数式编程语言（例如，Clojure）没有定义任何循环结构，而是仅依靠递归来重复调用代码。 可计算性理论证明，这些只递归的语言是图灵完备的； 这意味着它们与基于 while 和 for 等控制结构的命令式语言一样强大（它们可用于解决相同的问题）。
从自身内部重复调用一个函数可能会导致调用堆栈的大小等于所有涉及的调用的输入大小的总和。 由此可见，对于可以通过迭代轻松解决的问题，递归通常效率较低，对于大型问题，使用尾调用优化等优化技术是基础。
一种常见的算法设计策略是将问题划分为与原始问题类型相同的子问题，解决这些子问题，然后组合结果。 这通常被称为分而治之的方法； 当与存储先前解决的子问题的结果的查找表结合使用时（以避免重复解决它们并产生额外的计算时间），它可以称为动态规划或记忆。
一个递归函数定义有一个或多个基本情况，意思是函数产生结果的输入（不重复），和一个或多个递归情况，意思是程序重复（调用自己）的输入 . 例如，阶乘函数可以通过方程 0! = 1 并且，对于所有 n > 0，n！ = n(n − 1)!。 这两个方程本身都不能构成完整的定义； xxx个是基本情况，第二个是递归情况。 因为基本案例打破了递归链，它有时也被称为终止案例。
递归案例的工作可以看作是将复杂的输入分解为更简单的输入。 在正确设计的递归函数中，对于每次递归调用，输入问题必须以最终必须达到基本情况的方式进行简化。 （在正常情况下不打算终止的函数——例如，一些系统和服务器进程——是一个例外。）忽略编写一个基本案例，或者不正确地测试它，可能会导致无限循环。
对于某些函数（例如计算 e = 1/0！+ 1/1！+ 1/2！+ 1/3！+ ... 的系列），输入数据没有隐含明显的基本情况 ; 对于这些，可以添加一个参数（例如在我们的系列示例中要添加的术语数）以提供建立基本案例的“停止标准”。 corecursion 更自然地处理这样的例子，其中输出中的连续项是部分和； 这可以通过使用索引参数来计算第 n 个项（第 n 个部分和）来转换为递归。
许多计算机程序必须处理或生成任意数量的数据。 递归是一种表示程序员不知道确切大小的数据的技术：程序员可以使用自引用定义来指定此数据。 有两种类型的自指定义：归纳定义和共归纳定义。
归纳定义的递归数据定义是指定如何构造数据实例的定义。 例如，可以归纳地定义链表（这里使用 Haskell 语法）：
数据 ListOfStrings = EmptyList | 缺点 String ListOfStrings
上面的代码指定一个字符串列表为空，或者指定一个包含一个字符串和一个字符串列表的结构。 定义中的自引用允许构造任意（有限）数量的字符串列表。
归纳定义的另一个例子是自然数（或正整数）：
自然数是 1 或 n+1，其中 n 是自然数。
类似地，递归定义通常用于对编程语言中的表达式和语句的结构建模。
内容由aaa提供，本内容不代表词条百科立场，内容投诉举报请联系词条百科客服。如若转载，请注明出处82
