递归

递归（形容词：递归）发生在根据自身或其类型定义事物时。 递归用于从语言学到逻辑学的各种学科。 递归最常见的应用是在数学和计算机科学中，其中定义的函数在其自己的定义中应用。 虽然这显然定义了无限数量的实例（函数值），但它通常以不会发生无限循环或无限引用链（crock 递归）的方式完成。

在数学和计算机科学中，一类对象或方法在可以由两个属性定义时表现出递归行为：

• 一个简单的基本案例（或多个案例）——一个不使用递归来产生答案的终止场景
• 递归步骤 - 一组规则，可将所有连续案例减少到基本案例。

例如，下面是一个人的祖先的递归定义。 一个人的祖先是：

• 一个人的父母（基本情况），或
• 一个人的父母的祖先（递归步骤）。

斐波那契数列是递归的另一个经典例子：

Fib(0) = 0 作为基本情况 1，Fib(1) = 1 作为基本情况 2，对于所有整数 n >; 1, Fib(n) = Fib(n − 1) + Fib(n − 2)。

许多数学公理都基于递归规则。 例如皮亚诺公理对自然数的形式化定义可以描述为：零是一个自然数，每个自然数都有一个后继，也就是一个自然数。 通过这种基本情况和递归规则，可以生成所有自然数的集合。

其他递归定义的数学对象包括阶乘、函数（例如，递归关系）、集合（例如，康托尔三元集）和分形。

递归有各种更多的半开玩笑的定义； 参见递归幽默。

递归是当过程的步骤之一涉及调用过程本身时过程所经历的过程。 经过递归的过程被称为“递归的”。

要理解递归，必须认识到过程和过程的运行之间的区别。 程序是基于一组规则的一组步骤，而程序的运行涉及实际遵循规则并执行这些步骤。

递归与过程规范中对其他过程执行的引用有关，但不相同。

当这样定义过程时，这会立即产生无限循环的可能性； 如果在某些情况下跳过相关步骤以便完成过程，则递归只能在定义中正确使用。 递归有直接、间接和循环三种形式。 直接递归是函数 (A) 调用自身（A 引用 A）； 间接递归发生在一个函数 (A) 调用 (B)、函数 (B) 调用函数 (C)、函数 (C) 调用 (D) 等时，直到链中的一个函数调用更早的函数。 当函数 (A) 和函数 (B) 相互调用时，就会发生循环递归。 如果在直接递归、间接递归或循环递归中出现死循环，则称其为crock递归条件。 基本上有两种方法可以防止 crock 递归，要么限制函数可以引用自身的次数，要么对函数调用的深度设置xxx限制，例如 如果深度限制为 50，则任何时候一个过程调用另一个过程时，计数器都会增加； 当它退出时，该计数器会减少。 一旦计数器达到限制（在本例中为 50），则不允许进一步的过程调用； 如果尝试调用第 51 个函数，则操作终止。 使用递归限制只能防止 crock 递归； 除了停止 crock 递归之外，设置调用限制可能会产生副作用，即阻止执行深度嵌套但不是递归的合法复杂过程。

但是即使定义得当，递归过程对人类来说也不容易执行，因为它需要区分新的和旧的、部分执行的过程调用； 这需要对程序的各种同步实例的进展情况进行一些管理。 出于这个原因，递归定义在日常情况下非常少见。

语言学家诺姆·乔姆斯基 (Noam Chomsky) 和其他许多人认为，一种语言中的语法句子数量没有上限，语法句子长度也没有上限（超出实际限制，例如可以说出一个句子的时间） ), 可以解释为自然语言递归的结果。

这可以根据句法类别（例如句子）的递归定义来理解。