遞歸

遞歸（英語：Recursion），又譯為遞迴，在數學與電腦科學中，是指在函數的定義中使用函數自身的方法。遞歸一詞還較常用於描述以自相似方法重複事物的過程。例如，當兩面鏡子相互之間近似平行時，鏡中巢狀的圖像是以無限遞歸的形式出現的。也可以理解為自我複製的過程。

此條目講述的是遞歸的概念。關於另一部同名小說，參見遞歸 (小說)。關於電腦程式設計，參見遞歸 (電腦科學)。其他用法，參見遞歸 (消歧義)。

德羅斯特效應是遞歸的一種視覺形式。圖中女性手持的物體中有一幅她本人手持同一物體的小圖片，進而小圖片中還有更小的一幅她手持同一物體的圖片，依此類推。

正式定義

在數學和電腦科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類物件或方法，並規定其他所有情況都能被還原為其基本情況。

例如，下列為某人祖先的遞歸定義：

• 某人的雙親是他的祖先（基本情況）。
• 某人祖先的雙親同樣是某人的祖先（遞歸步驟）。

斐波那契數列是典型的遞歸案例：

• ${\displaystyle F_{0}=0}$（初始值）
• ${\displaystyle F_{1}=1}$（初始值）
• 對所有大於1的整數n：${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$（遞歸定義）

儘管有許多數學函數均可以遞歸表示，但在實際應用中，遞歸定義的高開銷往往會讓人望而卻步。例如：

• ${\displaystyle 0!=1}$（初始值）
• 對所有大於0的整數n：${\displaystyle n!=n\times (n-1)!}$（遞歸定義）

一種便於理解的心理模型，是認為遞歸定義對物件的定義是按照「先前定義的」同類物件來定義的。例如：你怎樣才能移動100個箱子？答案：你首先移動一個箱子，並記下它移動到的位置，然後再去解決較小的問題：你怎樣才能移動99個箱子？最終，你的問題將變為怎樣移動一個箱子，而這時你已經知道該怎麼做的。

如此的定義在數學中十分常見。例如，集合論對自然數的正式定義是：1是一個自然數，每個自然數都有一個後繼，這一個後繼也是自然數。

以下是另一個可能更有利於理解遞歸過程的解釋：

1. 我們已經完成了嗎？如果完成了，返回結果。如果沒有這樣的終止條件，遞歸將會永遠地繼續下去。
2. 如果沒有，則簡化問題，解決較容易的問題，並將結果組裝成原始問題的解決辦法。然後返回該解決辦法。

這樣就有一種更有趣的描述：「為了理解遞歸，則必須首先理解遞歸。」或者更準確地，按照安德魯·普洛特金（英語：Andrew Plotkin）的解釋：「如果你已經知道了什麼是遞歸，只需記住答案。否則，找一個比你更接近侯世達的人；然後讓他／她來告訴你什麼是遞歸。」^[1]

數學中常見的以遞歸形式定義的案例參見函數、集合以及分形等。

舉例：編寫一個程式使用遞歸求n的階乘：

Haskell:

fac 0 = 1
fac n = n * fac (n-1)

main = print( fac 10 )

語言中的例子

1. 從前有座山，山裏有座廟，廟裏有個老和尚，正在給小和尚講故事呢！故事是什麼呢？「從前有座山，山裏有座廟，廟裏有個老和尚，正在給小和尚講故事呢！故事是什麼呢？『從前有座山，山裏有座廟，廟裏有個老和尚，正在給小和尚講故事呢！故事是什麼呢？……』」
2. 一隻狗來到廚房，偷走一小塊麵包。廚子舉起杓子，把那隻狗打死了。於是所有的狗都跑來了，給那隻狗掘了一個墳墓，還在墓碑上刻了墓誌銘，讓未來的狗可以看到：「一隻狗來到廚房，偷走一小塊麵包。廚子舉起杓子，把那隻狗打死了。於是所有的狗都跑來了，給那隻狗掘了一個墳墓，還在墓碑上刻了墓誌銘，讓未來的狗可以看到：『一隻狗來到廚房，偷走一小塊麵包。廚子舉起杓子，把那隻狗打死了。於是所有的狗都跑來了，給那隻狗掘了一個墳墓，還在墓碑上刻了墓誌銘，讓未來的狗可以看到……』」
3. 大雄在房裏，用時光電視看着從前的情況。電視畫面中的那個時候，他正在房裏，用時光電視，看着從前的情況。電視畫面中的電視畫面的那個時候，他正在房裏，用時光電視，看着從前的情況……

數學之應用

謝爾賓斯基三角形-由封閉遞歸的三角形所形成之分形

遞歸定義集

主條目：遞歸定義

實例：自然數

關於遞歸定義集的經典範例，可透過自然數來說明：

${\displaystyle 0\in \mathbb {N} }$

若${\displaystyle n\in \mathbb {N} }$， 則${\displaystyle n+1\in \mathbb {N} }$

滿足上述兩個條件之最小集合，即為自然數集合

實例：可導出的命題集合

另一個有趣範例為，公理系統中，所有可導出命題之集合

• 若一個命題為公理，則其為可導出之命題
• 透過推理規則方式，若一個命題可以從可導出之命題所推論，則其為可導出之命題
• 滿足上述條件之最小集合，為可導出之命題之集合

此集合稱為，可導出之命題之集合，因為在數學基礎方法中，依非建立性法構建的命題之集合，可能大於由公理系統及推理規則所遞歸構建出之集合，詳細請參見 哥德爾不完備定理

有限次分割法

主條目：Finite subdivision rule

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

參見

• 分形
• 差分
• 遞歸關係式
• 塔珀自指公式
• 無限反射鏡

參考文獻

註腳

1. 原文：「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 （頁面存檔備份，存於互聯網檔案館）