递归

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

1. 简单的基线条件---不使用递归产生答案的终止情况
2. 一组规则将所有其他情形缩减到基线条件

例如，以下是某人祖先的递归定义:

• 某人的父母是他的祖先（基线条件）
• 某人祖先的祖先也是他的祖先（递归步骤）

斐波那契数列是递归的经典例子:

Fib(0) = 1  基线条件1；

Fib(1) = 1  基线条件2；

对所有整数n,n > 1时：Fib(n) = (Fib(n-1) + Fib(n-2))。

许多数学公理基于递归规则。例如，皮亚诺公理对自然数的形式定义可以描述为:0是自然数，每个自然数都有一个后继数，它也是自然数。通过这种基线条件和递归规则，可以生成所有自然数的集合。

递归定义的数学对象包括函数、集合，尤其是分形。

递归还有多种开玩笑的“定义”。

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

要理解递归，必须认识到程序和程序运行之间的区别。程序是基于一组规则的一组步骤。程序的运行实际上包括遵循规则和执行步骤。一个类比:一个程序就像一个书面的食谱；运行一个程序就像实际准备饭菜一样。

递归与过程规范中对其他程序执行的引用相关，但不相同。例如，食谱可能指烹饪蔬菜，而需要依次加水等步骤是另一个程序。然而，递归过程是指(至少)其中一个步骤需要一个相同过程的新实例，就像酸面团配方需要上次制作相同配方时剩下的一些面团。这立即产生了一个无限循环的可能性；如果为了程序能够完成，在某些情况下跳过有问题的步骤，这样递归只能在定义中被正确使用，比如一个酸面团配方，它还告诉您如何获取一些生面团，以防您以前从未做过生面团。即使定义正确，递归过程对人类来说也不容易执行，因为它需要区分过程的新调用和旧调用(部分执行)；这需要对程序的各种同步实例的进展程度进行一些管理。因此，递归定义在日常情况下非常罕见。一个例子可以是下面的寻找迷宫之路的过程，继续前进，直到到达出口或分支点(死角被认为是带有0个分支的分支点)。如果到达的点是出口，终止。否则，递归地使用该过程，依次尝试每个分支；如果每次试验都只到达死胡同而失败，返回到导致这个分支点的路径并报告失败。这是否真正定义了终止过程取决于迷宫的性质:它不允许循环。在任何情况下，执行该过程都需要仔细记录所有当前探索的分支点，以及哪些分支已经被彻底尝试过。

语言学家诺姆·乔姆斯基和其他许多人都认为，一种语言中语法句子数量没有上限，语法句子长度也没有上限(超出了实际的限制，例如说出来的时间)，这可以解释为自然语言中递归的结果。^[1][2] 这可以用句法范畴的递归定义来理解，例如句子，一个句子可以有一个结构，在这个结构中，跟在动词后面的是另一个句子:多萝西认为女巫是危险的，在这个结构中，女巫是危险一句出现在更大的句子中。因此，一个句子可以递归地(非常粗略地)定义为一个结构，包括一个名词短语、一个动词和可选的另一个句子。这实际上只是递归数学定义的一个特例。

这提供了一种理解语言创造的方法——无限数量的语法句子——因为它立即预言句子可以是任意长度的:多萝西认为托托怀疑铁皮人说的....除了可以递归定义的句子之外，还有许多结构，因此一个句子可以通过许多方式将一个类别的实例嵌入另一个类别。多年来，一般来说，语言都被证明适合这种分析。

然而，最近，丹尼尔·埃弗雷特基于他对皮拉汉语的主张，对递归是人类语言的一个基本属性这一普遍接受的观点提出了挑战。Andrew Nevins, David Pesetsky 和 Cilene Rodrigues是许多反对这一观点的人之一。^[3] 在任何情况下，文学自我引用都可以被认为不同于数学或逻辑递归。  ^[4]

递归不仅在语法中起着至关重要的作用，在自然语言语义中也是如此。例如，单词and可以理解为一种功能，它可以应用于句子含义，从而创造出新的句子，同样也可以用于名词短语含义、动词短语含义和其它。它也适用于不及物动词、及物动词或双及物动词。为了给它提供一个适当灵活的单一表示，并且通常被定义为使得它可以将这些不同类型的含义中的任何一种作为参数。这可以通过为一个简单的案例定义它来实现，在这个案例中，它组合了句子，然后根据简单的案例递归地定义其他案例。^[5]

递归语法是一种包含递归生成规则的形式语法。^[6]

3.1 递归幽默

递归有时在计算机科学、程序设计、哲学或数学教科书中幽默地使用，通常是通过给出循环定义或自我引用，在循环定义或自我引用中，假定的递归步骤不会更接近基线条件，而是导致无限回归。这样的书在词汇表中包含一个笑话条目并不罕见，大致如下:

递归。      ^[7]

Brian Kernighan 和Dennis Ritchie的书《C编程语言》的一些版本的索引在第269页有所变化；索引条目递归引用自身(“递归86、139、141、182、202、269”)。这个笑话的最早版本出现在Kernighan和Plauger的“软件工具”中，也出现在Kernighan和Pike的“UNIX编程环境”中。它没有出现在第一版的《C编程语言》中。

另一个笑话是“要理解递归，你必须理解递归。”^[7] 在谷歌网络搜索引擎的英文版本中，当搜索“递归”时，网站会提示“你的意思是:递归？”Andrew Plotkin的另一种形式如下:“如果你已经知道递归是什么，就记住答案。否则，找一个比你更靠近道Douglas Hofstadter 的人；然后问他或她什么是递归。”

递归首字母缩写也可以是递归幽默的例子。例如，PHP代表“PHP Hypertext Preprocessor”，WINE代表“WINE Is Not an Emulator.”，GNU代表“GNU's not Unix”。

谢尔宾斯基三角形—形成分形的三角形的有限递归。

4.1 递归定义的集合

例子:自然数

递归定义集合的典型例子由自然数给出:

0是自然数；

如果n是自然数，那么n+1也是自然数；

自然数集合是满足前两个属性的最小集合。

例子:真正可达命题的集合

另一个有趣的例子是公理系统中所有“真正可达”命题的集合。

• 如果一个命题是公理，它就是一个真正可达的命题。
• 如果一个命题可以通过推理规则从真正可达命题中获得，那么它就是真正可达命题。
• 真正可达命题集是满足这些条件的最小命题集。

这个集合被称为“真正可达命题”，因为在数学基础的非建设性方法中，真正命题的集合可能大于由公理和推理规则递归构造的集合。

4.2 有限细分规则

有限细分规则是递归的几何形式，可用于创建类似分形的图像。细分规则从由有限多个标签标记的多边形集合开始，然后以仅依赖于原始多边形标签的方式将每个多边形细分为更小的标记多边形，这个过程可被迭代。创建康托集合的标准“中间三分之一”技术是细分规则，重心细分也是细分规则。

4.3 函数递归

一个函数可以根据自身被部分地定义。一个常见的例子是斐波那契数列: F(n) = F(n − 1) + F(n − 2)。为了使这样的定义有用，它必须引入非递归定义的值，在这种情况下，F(0) = 0，F(1) = 1。

一个著名的递归函数是阿克曼函数，它不同于斐波那契数列，如果没有递归，它将无法被表达的。

4.4 涉及递归定义的证明

如前几节所述，将标准的案例证明技术应用于递归定义的集合或函数，会产生结构归纳法，这是数学归纳法的一种强有力的推广，广泛用于数学逻辑和计算机科学中的推导证明。

4.5 递归优化

动态规划是一种优化方法，它以递归的形式重述了多阶段或多步骤优化问题。动态规划的关键结果是贝尔曼方程(Bellman equation)，它将优化问题早期(或较早步骤)的值写入到后期(或较晚步骤)的值中。

4.6 递归定理

在集合论中，这是一个保证递归定义函数存在的定理。给定一个集合X,集合X中的一个元素a和一个函数f: X -->X，定理表明存在一个唯一的函数F：N-->X（N表示包括0的自然数集合），使得满足F(0)=a , F(n+1)=f(F(n)) (对于任何自然数n)。

唯一性的证明

取两个函数F：N-->X和G：N-->X使得满足：

F(0)=a

G(0)=a

F(n+1)=f(F(n))

G(n+1)=f(G(n))

其中a是集合X中的一个元素。

数学归纳法可以证明对于所有自然数都有F(n)=G(n)：

基线条件：当n=0时，等式F(0)=a=G(0)成立；

递归步骤：假设当k∈N时，F(k)=G(K)成立,然后F(k+1)=f(F(k))=f(G(k))=G(k+1),因此F(k)=G(k)意味着F(k+1)=G(k+1)

通过归纳，F(n)=G(n)  (其中n∈N)。

一种常见的简化方法是将一个问题分成相同类型的子问题。作为一种计算机编程技术，这被称为分治法，是许多重要算法设计的关键。分治法是一种自上而下解决问题的方法，通过解决越来越小的实例来解决问题。相反的方法是动态编程，这种方法是自下而上的方法，通过解决越来越大的实例来解决问题，直到达到所需的大小。

递归的一个经典例子是阶乘函数的定义，这里用C代码给出:

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

该函数在输入的较小版本（n-1）上递归调用自身，并将递归调用的结果乘以n，直到达到基线条件，类似于阶乘的数学定义。

当一个函数被定义为更简单、通常更小的自身时，计算机编程中的递归就是一个例子。然后通过组合从问题的简单版本中获得的解决方案来设计问题的解决方案。递归的一个示例应用是在编程语言的解析器中。递归的最大优点是通过有限的计算机程序可以定义、解析或产生无限组可能的句子、设计或其他数据。

递推关系是递归定义一个或多个序列的方程，可以“解决”某些特定类型的递推关系来获得非递归定义。

递归娃娃：Zvyozdochkin和Malyutin的原始俄罗斯套娃，1892年

图为Stefaneschi Triptych（乔托 , 1320年）的正面，递归地包含自己的图像(由中央面板中跪着的图形支撑)。

俄罗斯娃娃或俄罗斯套娃是递归概念的一个物理艺术例子。^[8]

自1320年乔托的Stefaneschi三联画问世以来，递归就一直用于绘画。它的中央面板包含红衣主教Stefaneschi的跪像，举着三联画本身作为祭品。 ^[9]

M.C. Eschers 印刷画廊 (1956)描绘了一个扭曲的城市，其中包含一个递归包含图片的画廊，因此无限。^[10]