用戶:Danny037286/沙盒
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() |
遞歸(英語:Recursion),又譯為遞迴,在數學與電腦科學中,是指在函數的定義中使用函數自身的方法。遞歸一詞還較常用於描述以自相似方法重複事物的過程。例如,當兩面鏡子相互之間近似平行時,鏡中巢狀的圖像是以無限遞歸的形式出現的。也可以理解為自我複製的過程。
語言例子
從前有座山,山裏有座廟,廟裏有個老和尚,正在給小和尚講故事呢!故事是什麼呢?「從前有座山,山裏有座廟,廟裏有個老和尚,正在給小和尚講故事呢!故事是什麼呢?『從前有座山,山裏有座廟,廟裏有個老和尚,正在給小和尚講故事呢!故事是什麼呢?……』」
一隻狗來到廚房,偷走一小塊麵包。廚子舉起杓子,把那隻狗打死了。於是所有的狗都跑來了,給那隻狗掘了一個墳墓,還在墓碑上刻了墓誌銘,讓未來的狗可以看到:「一隻狗來到廚房,偷走一小塊麵包。廚子舉起杓子,把那隻狗打死了。於是所有的狗都跑來了,給那隻狗掘了一個墳墓,還在墓碑上刻了墓誌銘,讓未來的狗可以看到:『一隻狗來到廚房,偷走一小塊麵包。廚子舉起杓子,把那隻狗打死了。於是所有的狗都跑來了,給那隻狗掘了一個墳墓,還在墓碑上刻了墓誌銘,讓未來的狗可以看到……』」
正式定義
在數學和電腦科學中,遞歸指由一種(或多種)簡單的基本情況定義的一類對象或方法,並規定其他所有情況都能被還原為其基本情況。
例如,下列為某人祖先的遞歸定義:
斐波那契數列是典型的遞歸案例:
- (初始值)
- (初始值)
- 對所有大於1的整數n:(遞歸定義)
儘管有許多數學函數均可以遞歸表示,但在實際應用中,遞歸定義的高開銷往往會讓人望而卻步。例如:
- (初始值)
- 對所有大於0的整數n:(遞歸定義)
一種便於理解的心理模型,是認為遞歸定義對對象的定義是按照「先前定義的」同類對象來定義的。例如:你怎樣才能移動100個箱子?答案:你首先移動一個箱子,並記下它移動到的位置,然後再去解決較小的問題:你怎樣才能移動99個箱子?最終,你的問題將變為怎樣移動一個箱子,而這是你已經知道該怎麼做的。
如此的定義在數學中十分常見。例如,集合論對自然數的正式定義是:1是一個自然數,每個自然數都有一個後繼,這一個後繼也是自然數。
以下是另一個可能更有利於理解遞歸過程的解釋:
- 我們已經完成了嗎?如果完成了,返回結果。如果沒有這樣的終止條件,遞歸將會永遠地繼續下去。
- 如果沒有,則簡化問題,解決較容易的問題,並將結果組裝成原始問題的解決辦法。然後返回該解決辦法。
這樣就有一種更有趣的描述:「為了理解遞歸,則必須首先理解遞歸。」或者更準確地,按照安德魯·普洛特金的解釋:「如果你已經知道了什麼是遞歸,只需記住答案。否則,找一個比你更接近侯世達的人;然後讓他/她來告訴你什麼是遞歸。」[1]
電腦科學之應用
遞歸經常被用於解決電腦科學的問題。在一些程式語言(如Scheme、Haskell中),遞歸是進行迴圈的一種方法。
舉例: 編寫一個程式使用遞歸求n的階乘
fac 0 = 1
fac n = n * fac (n-1)
main = print( fac 10 )
數學上之應用
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/4/45/Sierpinski_triangle.svg/250px-Sierpinski_triangle.svg.png)
遞歸定義集
實例:自然數
關於遞歸定義集的經典範例,可透過自然數來說明
The canonical example of a recursively defined set is given by the natural numbers:
- 0 屬於自然數
- 若 n 屬於 , 則 n + 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
|