递归
Clash Royale CLAN TAG#URR8PPP 
德罗斯特效应是递归的一种视觉形式。图中女性手持的物体中有一幅她本人手持同一物体的小图片，进而小图片中还有更小的一幅她手持同一物体的图片，依此类推。
递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。
目录
1 语言例子
2 正式定义
3 電腦科學之應用
4 數學之應用
4.1 實例：自然數
4.2 實例：可導出的命題集合
4.3 有限次分割法
5 参见
6 参考文献
6.1 脚注
6.2 书目
7 外部链接
语言例子
从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？「从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？『从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……』」
一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓誌銘，让未来的狗可以看到：「一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓誌銘，让未来的狗可以看到：『一只狗来到厨房，偷走一小块面包。厨子举起杓子，把那只狗打死了。于是所有的狗都跑来了，给那只狗掘了一个坟墓，还在墓碑上刻了墓誌銘，让未来的狗可以看到……』」
大雄在房裏，用時光電視看着未來的情況。電視畫面中的那個時候，他正在用時光電視，看着未來的情況。電視畫面中的那個時候，他正在用時光電視，看着未來的情況……
正式定义
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
例如，下列为某人祖先的递归定义：
- 某人的双亲是他的祖先（基本情况）。
- 某人祖先的双亲同样是某人的祖先（递归步骤）。
斐波那契数列是典型的递归案例：
F0=0displaystyle F_0=0（初始值）
F1=1displaystyle F_1=1（初始值）
- 对所有大於1的整数n：Fn=Fn−1+Fn−2displaystyle F_n=F_n-1+F_n-2
（递归定义）
尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：
0!=1displaystyle 0!=1（初始值）
- 对所有大於0的整数n：n!=n×(n−1)!displaystyle n!=ntimes (n-1)!
（递归定义）
一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这是你已经知道该怎么做的。
如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。
以下是另一个可能更有利于理解递归过程的解释：
- 我们已经完成了吗？如果完成了，返回结果。如果没有这样的终止条件，递归将会永远地继续下去。
- 如果没有，则简化问题，解决较容易的问题，并将结果组装成原始问题的解决办法。然后返回该解决办法。
这样就有一种更有趣的描述：“为了理解递归，则必须首先理解递归。”或者更准确地，按照安德鲁·普洛特金的解释：“如果你已经知道了什么是递归，只需记住答案。否则，找一个比你更接近侯世达的人；然后让他／她来告诉你什么是递归。”[1]
数学中常见的以递归形式定义的案例参见函数、集合以及分形等。
電腦科學之應用
遞迴經常被用於解決電腦科學的問題。在一些程式語言（如Scheme、Haskell中），遞迴是進行迴圈的一種方法。
举例：
编写一个程序使用递归求n的阶乘
fac 0 = 1
fac n = n * fac (n-1)
main = print( fac 10 )
數學之應用
謝爾賓斯基三角形-由封閉遞歸的三角形所形成之碎形
遞歸定義集
實例：自然數
關於遞歸定義集的經典範例，可透過自然數來說明
The canonical example of a recursively defined set is given by the natural numbers:
- 0 屬於自然數 Ndisplaystyle mathbb N
- 若 n 屬於 Ndisplaystyle mathbb N
， 則 n + 1 亦屬於 Ndisplaystyle mathbb N
- 滿足上述兩個條件之最小集合，即為自然數集合
實例：可導出的命題集合
另一個有趣範例為，公理系統中，所有可導出命題之集合
- 若一個命題為公理，則其為可導出之命題
- 透過推理規則方式，若一個命題可以從可導出之命題所推論，則其為可導出之命題
- 滿足上述條件之最小集合，為可導出之命題之集合
此集合稱為，可導出之命題之集合，因為在數學基礎方法中，依非建立性法構建的命題之集合，可能大於由公理系統及推理規則所遞歸構建出之集合，詳細請參見 哥德爾不完備定理
有限次分割法
有限次分割法為幾何形式之遞歸，可用以創建類碎形之圖案。次分割原則的運作如後所述，從多個已被有限個標籤標註的多邊形開始，接著每個多邊形僅根據其標籤，繼續細切到更小的多邊形，此一細切的過程可不斷重複。
参见
- 分形
- 差分
- 遞迴關係式
- 塔珀自指公式
参考文献
脚注
^ 原文：“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.”
书目
Johnsonbaugh, Richard. Discrete Mathematics. Prentice Hall. 2004. ISBN 0-13-117686-2.
Hofstadter, Douglas. Gödel, Escher, Bach: an Eternal Golden Braid. Basic Books. 1999. ISBN 0-465-02656-7.
Shoenfield, Joseph R. Recursion Theory. A K Peters Ltd. 2000. ISBN 1-56881-149-7.
Causey, Robert L. Logic, Sets, and Recursion. Jones & Bartlett. 2001. ISBN 0-7637-1695-2.
Cori, Rene; Lascar, Daniel; Pelletier, Donald H. Recursion Theory, Godel's Theorems, Set Theory, Model Theory. Oxford University Press. 2001. ISBN 0-19-850050-5.
Barwise, Jon; Moss, Lawrence S. Vicious Circles. Stanford Univ Center for the Study of Language and Information. 1996. ISBN 0-19-850050-5. - offers a treatment of corecursion.
Rosen, Kenneth H. Discrete Mathematics and Its Applications. McGraw-Hill College. 2002. ISBN 0-07-293033-0.
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. Mit Pr. 2001. ISBN 0-262-03293-7.
Kernighan, B.; Ritchie, D. The C programming Language. Prentice Hall. 1988. ISBN 0-13-110362-8.
Stokey, Nancy,; Robert Lucas; Edward Prescott. Recursive Methods in Economic Dynamics. Harvard University Press. 1989. ISBN 0674750969.
外部链接
Recursion - tutorial by Alan Gauld
A Primer on Recursion- contains pointers to recursion in Formal Languages, Linguistics, Math and Computer Science- Google easter for recursion
| ||||||||||||||||||||||||||||||||||||||||
