『壹』 計算機裡面什麼是遞歸
在數學和計算機科學中,當一類對象或方法可以由兩個屬性定義時,它們表現出遞歸行為:
簡單的基線條件---不使用遞歸產生答案的終止情況
一組規則將所有其他情形縮減到基線條件
例如,以下是某人祖先的遞歸定義:
某人的父母是他的祖先(基線條件)
某人祖先的祖先也是他的祖先(遞歸步驟)
斐波那契數列是遞歸的經典例子:
Fib(0) = 1 基線條件1;
Fib(1) = 1 基線條件2;
對所有整數n,n > 1時:Fib(n) = (Fib(n-1) + Fib(n-2))。
許多數學公理基於遞歸規則。例如,皮亞諾公理對自然數的形式定義可以描述為:0是自然數,每個自然數都有一個後繼數,它也是自然數。通過這種基線條件和遞歸規則,可以生成所有自然數的集合。
遞歸定義的數學對象包括函數、集合,尤其是分形。
遞歸還有多種開玩笑的「定義」。
非正式定義
俄羅斯娃娃或俄羅斯套娃是遞歸概念的一個物理藝術例子。
自1320年喬托的Stefaneschi三聯畫問世以來,遞歸就一直用於繪畫。它的中央面板包含紅衣主教Stefaneschi的跪像,舉著三聯畫本身作為祭品。
M.C. Eschers 印刷畫廊 (1956)描繪了一個扭曲的城市,其中包含一個遞歸包含圖片的畫廊,因此無限。