查看“︁递归”︁的源代码

{{NoteTA
|G1 = IT
|G2 = Math
}}
{{dablink|此条目讲述的是递归的概念。关于另一部同名小说，参见[[递归 (小说)]]。关于计算机程序设计，参见[[递归 (计算机科学)]]。其他用法，参见[[递归 (消歧义)]]。}}

[[File:Droste.jpg|thumb|[[德罗斯特效应]]是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片，进而小图片中还有更小的一幅她手持同一物体的图片，依此类推。]]
'''递归'''（{{lang-en|Recursion}}），又译为'''-{zh-cn:递回; zh-tw:遞歸; zh-hk:遞迴;}-'''，在[[数学]]与[[计算机科学]]中，是指在[[函数]]的定义中使用函数自身的方法。递归一词还较常用于描述以[[自相似]]方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。

== 正式定义 ==
在[[数学]]和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

例如，下列为某人祖先的递归定义：
* 某人的[[双亲]]是他的[[祖先]]（基本情况）。
* 某人祖先的双亲同样是某人的祖先（递归步骤）。
[[斐波那契数列]]是典型的递归案例：

* <math>F_0=0</math>（初始值）
* <math>F_1=1</math>（初始值）
* 对所有大於1的整数n：<math>F_n=F_{n-1}+F_{n-2}</math>（递归定义）

尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：

* <math>0!=1</math>（初始值）
* 对所有大於0的整数n：<math>n!=n\times(n-1)!</math>（递归定义）

一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这时你已经知道该怎么做的。

如此的定义在数学中十分常见。例如，集合论对[[自然数]]的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。

以下是另一个可能更有利于理解递归过程的解释：

# 我们已经完成了吗？如果完成了，返回结果。如果没有这样的'''终止条件'''，递归将会永远地继续下去。
# 如果没有，则<u>简化</u>问题，解决较容易的问题，并将结果组装成原始问题的解决办法。然后返回该解决办法。 

这样就有一种更有趣的描述：“为了理解递归，则必须首先理解递归。”或者更准确地，按照{{link-en|安德鲁·普洛特金|Andrew Plotkin}}的解释：“如果你已经知道了什么是递归，只需记住答案。否则，找一个比你更接近[[侯世达]]的人；然后让他／她来告诉你什么是递归。”<ref>原文：“If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to [[Douglas Hofstadter]] than you are; then ask him or her what recursion is.”</ref>

数学中常见的以递归形式定义的案例参见函数、[[集合 (数学)|集合]]以及[[分形]]等。

举例：编写一个程序使用递归求n的[[階乘|阶乘]]：

Haskell:

<syntaxhighlight lang="haskell">
fac 0 = 1
fac n = n * fac (n-1)

main = print( fac 10 )
</syntaxhighlight>

== 语言中的例子 ==
#从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？「从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？『从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……』」
#一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓誌銘，让未来的狗可以看到：「一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓誌銘，让未来的狗可以看到：『一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓誌銘，让未来的狗可以看到……』」
#[[大雄]]在房裏，用時光電視看着从前的情況。電視畫面中的那個時候，他正在房裏，用時光電視，看着从前的情況。電視畫面中的電視畫面的那個時候，他正在房裏，用時光電視，看着从前的情況……

== 數學之應用 ==
[[File:Sierpinski_triangle.svg|thumb|250x250px| [[謝爾賓斯基三角形]]-由封閉遞歸的三角形所形成之[[碎形]] ]]

===遞歸定義集===
{{Main|遞歸定義}}

====實例：自然數====
關於遞歸定義集的經典範例，可透過[[自然數]]來說明：
: <math>0 \in \mathbb{N}</math>
: 若<math>n \in \mathbb{N}</math>， 則<math>n+1 \in \mathbb{N}</math>
: 滿足上述兩個條件之最小集合，即為自然數集合

====實例：可導出的命題集合====

另一個有趣範例為，[[公理系统|公理系統]]中，所有可導出命題之集合
* 若一個[[命題]]為[[公理]]，則其為可導出之命題
* 透過[[推理規則]]方式，若一個命題可以從可導出之命題所推論，則其為可導出之命題
* 滿足上述條件之最小集合，為可導出之命題之集合
此集合稱為，可導出之命題之集合，因為在數學基礎方法中，依非建立性法構建的命題之集合，可能大於由[[公理系統]]及[[推理規則]]所遞歸構建出之集合，詳細請參見 [[哥德爾不完備定理]]

===有限次分割法===
{{Main|{{en-link|有限次分割法|Finite subdivision rule}}}}
有限次分割法為幾何形式之遞歸，可用以創建類[[碎形]]之圖案。次分割原則的運作如後所述，從多個已被有限個標籤標註的多邊形開始，接著每個多邊形僅根據其標籤，繼續細切到更小的多邊形，此一細切的過程可不斷重複。

===递归定理===
在[[集合论]]中，递归定理保证递归定义的函数存在。给定一个集合<math>X</math>、<math>X</math>的一个元素<math>a</math>和一个函数<math>f: X \to X</math>，这个定理声称存在一个唯一的函数<math>F: \N \to X</math>，这里的<math>\N</math>指称包含零的[[自然数|自然数集]]，它使得对于任何自然数<math>n</math>有着：
:<math>F(0) = a</math>
:<math>F(n + 1) = f(F(n))</math>

[[理查德·戴德金|戴德金]]首次提出了通过递归在<math>\mathbb N</math>上定义集合论函数的唯一性问题，并在1888年文章《数是什么且有何用？》中进行了梗概论述<ref>A. Kanamori, "[https://math.bu.edu/people/aki/20.pdf In Praise of Replacement]", pp.50--52. Bulletin of Symbolic Logic, vol. 18, no. 1 (2012). Accessed 21 August 2023.</ref>。

====唯一性证明====
选取两个函数<math>F: \N \to X</math>和<math>G: \N \to X</math>使得：

:<math>F(0) = a</math>
:<math>G(0) = a</math>
:<math>F(n + 1) = f(F(n))</math>
:<math>G(n + 1) = f(G(n))</math>

这里的<math>a</math>是<math>X</math>的一个元素。

可以通过[[数学归纳法]]证明对于所有自然数<math>n</math>有着<math>F(n) = G(n)</math>：

:'''基础情况'''：<math>F(0) = a = G(0)</math>，所以等式对于<math>n = 0</math>成立。

:'''归纳步骤'''：假定对于某个{{nowrap|<math>k \in \N</math>}}有着<math>F(k) = G(k)</math>，那么<math>F(k + 1) = f(F(k)) = f(G(k)) = G(k + 1)</math>。
::因此<math>F(k) = G(k)</math>蕴涵了<math>F(k + 1) = G(k + 1)</math>。

通过归纳，对于所有<math>n \in \N</math>有着<math>F(n) = G(n)</math>。

== 参见 ==
* [[分形]]
* [[差分]]
* [[遞迴關係式]]
* [[塔珀自指公式]]
* [[无限反射镜]]

== 参考文献 ==

=== 脚注 ===
<references />

=== 书目 ===
* {{cite book|title=Discrete Mathematics|publisher=Prentice Hall|year=2004|isbn=0-13-117686-2|author=Johnsonbaugh, Richard}}
* {{cite book|title=Gödel, Escher, Bach: an Eternal Golden Braid|publisher=Basic Books|year=1999|isbn=0-465-02656-7|author=Hofstadter, Douglas}}
* {{cite book|title=Recursion Theory|publisher=A K Peters Ltd|year=2000|isbn=1-56881-149-7|author=Shoenfield, Joseph R.}}
* {{cite book|title=Logic, Sets, and Recursion|url=https://archive.org/details/logicsetsrecursi0000caus|publisher=Jones & Bartlett|year=2001|isbn=0-7637-1695-2|author=Causey, Robert L.}}
* {{cite book|title=Recursion Theory, Godel's Theorems, Set Theory, Model Theory|publisher=Oxford University Press|year=2001|isbn=0-19-850050-5|author=Cori, Rene; Lascar, Daniel; Pelletier, Donald H.}}
* {{cite book|title=Vicious Circles|publisher=Stanford Univ Center for the Study of Language and Information|year=1996|isbn=0-19-850050-5|author=Barwise, Jon; Moss, Lawrence S.}}  - offers a treatment of corecursion.
* {{cite book|title=Discrete Mathematics and Its Applications|url=https://archive.org/details/discretemathemat0000kenn_d9b0|publisher=McGraw-Hill College|year=2002|isbn=0-07-293033-0|author=Rosen, Kenneth H.}}
* {{cite book|title=Introduction to Algorithms|publisher=Mit Pr|year=2001|isbn=0-262-03293-7|author=Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein}}
* {{cite book|title=The C programming Language|publisher=Prentice Hall|year=1988|isbn=0-13-110362-8|author=Kernighan, B.; Ritchie, D.}}
* {{cite book|title=Recursive Methods in Economic Dynamics|url=https://archive.org/details/recursivemethods0000stok|publisher=Harvard University Press|year=1989|isbn=0674750969|author=Stokey, Nancy,; Robert Lucas; Edward Prescott}}

== 外部链接 ==
* [https://web.archive.org/web/20050206051223/http://www.freenetpages.co.uk/hp/alan.gauld/tutrecur.htm Recursion] - tutorial by Alan Gauld
* [http://amitksaha.files.wordpress.com/2009/05/recursion-primer.pdf A Primer on Recursion] {{Wayback|url=http://amitksaha.files.wordpress.com/2009/05/recursion-primer.pdf |date=20110718093344 }}- contains pointers to recursion in Formal Languages, Linguistics, Math and Computer Science
* [http://www.gtricks.com/google-tricks/funny-recursion-loop-display/ Google easter for recursion] {{Wayback|url=http://www.gtricks.com/google-tricks/funny-recursion-loop-display/ |date=20170110034401 }}

{{分形}}

[[Category:數理邏輯]]
[[Category:計算理論]]
[[Category:递归]]