计算机中递归的概念,递归是什么?关于递归的详细介绍
计算机中递归的概念，递归是什么？关于递归的详细介绍
递归，⼜译为递回，在数学与计算机科学中，是指在函数的定义中使⽤函数⾃⾝的⽅法。递归⼀词还较常⽤于描述以⾃相似⽅法重复事物的过程。例如，当两⾯镜⼦相互之间近似平⾏时，镜中嵌套的图像是以⽆限递归的形式出现的。也可以理解为⾃我复制的过程。
正式的定义
在数学和计算机科学中，当⼀类对象或⽅法可以由两个属性定义时，它们表现出递归⾏为:
什么是自然数简单的基线条件---不使⽤递归产⽣答案的终⽌情况
⼀组规则将所有其他情形缩减到基线条件
例如，以下是某⼈祖先的递归定义:
某⼈的⽗母是他的祖先(基线条件)
某⼈祖先的祖先也是他的祖先(递归步骤)
斐波那契数列是递归的经典例⼦:
Fib(0) = 1 基线条件1；
Fib(1) = 1 基线条件2；
对所有整数n,n > 1时：Fib(n) = (Fib(n-1) + Fib(n-2))。
许多数学公理基于递归规则。例如，⽪亚诺公理对⾃然数的形式定义可以描述为:0是⾃然数，每个⾃然数都有⼀个后继数，它也是⾃然数。通过这种基线条件和递归规则，可以⽣成所有⾃然数的集合。
递归定义的数学对象包括函数、集合，尤其是分形。
递归还有多种开玩笑的“定义”。
⾮正式定义
递归是当程序的⼀个步骤涉及调⽤程序本⾝的过程。经历递归的过程被称为“递归”。
要理解递归，必须认识到程序和程序运⾏之间的区别。程序是基于⼀组规则的⼀组步骤。程序的运⾏
实际上包括遵循规则和执⾏步骤。⼀个类⽐:⼀个程序就像⼀个书⾯的⾷谱；运⾏⼀个程序就像实际准备饭菜⼀样。
递归与过程规范中对其他程序执⾏的引⽤相关，但不相同。例如，⾷谱可能指烹饪蔬菜，⽽需要依次加⽔等步骤是另⼀个程序。然⽽，递归过程是指(⾄少)其中⼀个步骤需要⼀个相同过程的新实例，就像酸⾯团配⽅需要上次制作相同配⽅时剩下的⼀些⾯团。这⽴即产⽣了⼀个⽆限循环的可能性；如果为了程序能够完成，在某些情况下跳过有问题的步骤，这样递归只能在定义中被正确使⽤，⽐如⼀个酸⾯团配⽅，它还告诉您如何获取⼀些⽣⾯团，以防您以前从未做过⽣⾯团。即使定义正确，递归过程对⼈类来说也不容易执⾏，因为它需要区分过程的新调⽤和旧调⽤(部分执⾏)；这需要对程序的各种同步实例的进展程度进⾏⼀些管理。因此，递归定义在⽇常情况下⾮常罕见。⼀个例⼦可以是下⾯的寻迷宫之路的过程，继续前进，直到到达出⼝或分⽀点(死⾓被认为是带有0个分⽀的分⽀点)。如果到达的点是出⼝，终⽌。否则，递归地使⽤该过程，依次尝试每个分⽀；如果每次试验都只到达死胡同⽽失败，返回到导致这个分⽀点的路径并报告失败。这是否真正定义了终⽌过程取决于迷宫的性质：它不允许循环。在任何情况下，执⾏该过程都需要仔细记录所有当前探索的分⽀点，以及哪些分⽀已经被彻底尝试过。
在语⾔中
语⾔学家诺姆·乔姆斯基和其他许多⼈都认为，⼀种语⾔中语法句⼦数量没有上限，语法句⼦长度也没有上限(超出了实际的限制，例如说出来的时间)，这可以解释为⾃然语⾔中递归的结果。 这可以⽤句法范畴的递归定义来理解，例如句⼦，⼀个句⼦可以有⼀个结构，在这个结构中，跟在动词后⾯的是另⼀个句⼦：多萝西认为⼥巫是危险的，在这个结构中，⼥巫是危险⼀句出现在更⼤的句⼦中。因此，⼀个句⼦可以递归地(⾮常粗略地)定义为⼀个结构，包括⼀个名词短语、⼀个动词和可选的另⼀个句⼦。这实际上只是递归数学定义的⼀个特例。
这提供了⼀种理解语⾔创造的⽅法——⽆限数量的语法句⼦——因为它⽴即预⾔句⼦可以是任意长度的：多萝西认为托托怀疑铁⽪⼈说的....除了可以递归定义的句⼦之外，还有许多结构，因此⼀个句⼦可以通过许多⽅式将⼀个类别的实例嵌⼊另⼀个类别。多年来，⼀般来说，语⾔都被证明适合这种分析。
然⽽，最近，丹尼尔·埃弗雷特基于他对⽪拉汉语的主张，对递归是⼈类语⾔的⼀个基本属性这⼀普遍接受的观点提出了挑战。Andrew Nevins, David Pesetsky 和 Cilene Rodrigues是许多反对这⼀观点的⼈之⼀。 在任何情况下，⽂学⾃我引⽤都可以被认为不同于数学或逻辑递归。
递归不仅在语法中起着⾄关重要的作⽤，在⾃然语⾔语义中也是如此。例如，单词and可以理解为⼀种功能，它可以应⽤于句⼦含义，从⽽创造出新的句⼦，同样也可以⽤于名词短语含义、动词短语含义
和其它。它也适⽤于不及物动词、及物动词或双及物动词。为了给它提供⼀个适当灵活的单⼀表⽰，并且通常被定义为使得它可以将这些不同类型的含义中的任何⼀种作为参数。这可以通过为⼀个简单的案例定义它来实现，在这个案例中，它组合了句⼦，然后根据简单的案例递归地定义其他案例。
递归语法是⼀种包含递归⽣成规则的形式语法。
递归幽默
递归有时在计算机科学、程序设计、哲学或数学教科书中幽默地使⽤，通常是通过给出循环定义或⾃我引⽤，在循环定义或⾃我引⽤中，假定的递归步骤不会更接近基线条件，⽽是导致⽆限回归。这样的书在词汇表中包含⼀个笑话条⽬并不罕见，⼤致如下：
另⼀个笑话是“要理解递归，你必须理解递归。” 在⾕歌⽹络搜索引擎的英⽂版本中，当搜索“递归”时，⽹站会提⽰“你的意思是：递归？”Andrew Plotkin的另⼀种形式如下:“如果你已经知道递归是什么，就记住答案。否则，⼀个⽐你更靠近道Douglas Hofstadter 的⼈；然后问他或她什么是递归。”
递归⾸字母缩写也可以是递归幽默的例⼦。例如，PHP代表“PHP Hypertext Preprocessor”，WINE代表“WINE Is Not an Emulator.”，GNU代表“GNU's not Unix”。
在数学中
递归定义的集合
例⼦:⾃然数
递归定义集合的典型例⼦由⾃然数给出:
0是⾃然数；
如果n是⾃然数，那么n+1也是⾃然数；
⾃然数集合是满⾜前两个属性的最⼩集合。
例⼦：真正可达命题的集合
另⼀个有趣的例⼦是公理系统中所有“真正可达”命题的集合。
如果⼀个命题是公理，它就是⼀个真正可达的命题。
如果⼀个命题可以通过推理规则从真正可达命题中获得，那么它就是真正可达命题。
真正可达命题集是满⾜这些条件的最⼩命题集。
这个集合被称为“真正可达命题”，因为在数学基础的⾮建设性⽅法中，真正命题的集合可能⼤于由公理和推理规则递归构造的集合。有限细分规则
有限细分规则是递归的⼏何形式，可⽤于创建类似分形的图像。细分规则从由有限多个标签标记的多边形集合开始，然后以仅依赖于原始多边形标签的⽅式将每个多边形细分为更⼩的标记多边形，这个过程可被迭代。创建康托集合的标准“中间三分之⼀”技术是细分规则，重⼼细分也是细分规则。函数递归
⼀个函数可以根据⾃⾝被部分地定义。⼀个常见的例⼦是斐波那契数列: F(n) = F(n − 1) + F(n − 2)。为了使这样的定义有⽤，它必须引⼊⾮递归定义的值，在这种情况下，F(0) = 0，F(1) = 1。
⼀个著名的递归函数是阿克曼函数，它不同于斐波那契数列，如果没有递归，它将⽆法被表达的。涉及递归定义的证明
如前⼏节所述，将标准的案例证明技术应⽤于递归定义的集合或函数，会产⽣结构归纳法，这是数学归纳法的⼀种强有⼒的推⼴，⼴泛⽤于数学逻辑和计算机科学中的推导证明。递归优化
动态规划是⼀种优化⽅法，它以递归的形式重述了多阶段或多步骤优化问题。动态规划的关键结果是贝尔曼⽅程(Bellman equation)，它将优化问题早期(或较早步骤)的值写⼊到后期(或较晚步骤)的值中。递归定理
在集合论中，这是⼀个保证递归定义函数存在的定理。给定⼀个集合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，直到达到基线条件，类似于阶乘的数学定义。
当⼀个函数被定义为更简单、通常更⼩的⾃⾝时，计算机编程中的递归就是⼀个例⼦。然后通过组合从问题的简单版本中获得的解决⽅案来设计问题的解决⽅案。递归的⼀个⽰例应⽤是在编程语⾔的解析器中。递归的最⼤优点是通过有限的计算机程序可以定义、解析或产⽣⽆限组可能的句⼦、设计或其他数据。
递推关系是递归定义⼀个或多个序列的⽅程，可以“解决”某些特定类型的递推关系来获得⾮递归定义。
在艺术领域
俄罗斯娃娃或俄罗斯套娃是递归概念的⼀个物理艺术例⼦。
⾃1320年乔托的Stefaneschi三联画问世以来，递归就⼀直⽤于绘画。它的中央⾯板包含红⾐主教Stefaneschi的跪像，举着三联画本⾝作为祭品。
M.C. Eschers 印刷画廊 (1956)描绘了⼀个扭曲的城市，其中包含⼀个递归包含图⽚的画廊，因此⽆限。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。