遞歸
編輯遞歸(形容詞:遞歸)發生在根據自身或其類型定義事物時。 遞歸用于從語言學到邏輯學的各種學科。 遞歸最常見的應用是在數學和計算機科學中,其中定義的函數在其自己的定義中應用。 雖然這顯然定義了無限數量的實例(函數值),但它通常以不會發生無限循環或無限引用鏈(crock 遞歸)的方式完成。
正式定義
編輯在數學和計算機科學中,一類對象或方法在可以由兩個屬性定義時表現出遞歸行為:
- 一個簡單的基本案例(或多個案例)——一個不使用遞歸來產生答案的終止場景
- 遞歸步驟 - 一組規則,可將所有連續案例減少到基本案例。
例如,下面是一個人的祖先的遞歸定義。 一個人的祖先是:
- 一個人的父母(基本情況),或
- 一個人的父母的祖先(遞歸步驟)。
斐波那契數列是遞歸的另一個經典例子:
Fib(0) = 0 作為基本情況 1,Fib(1) = 1 作為基本情況 2,對于所有整數 n >; 1, Fib(n) = Fib(n ? 1) + Fib(n ? 2)。
許多數學公理都基于遞歸規則。 例如皮亞諾公理對自然數的形式化定義可以描述為:零是一個自然數,每個自然數都有一個后繼,也就是一個自然數。 通過這種基本情況和遞歸規則,可以生成所有自然數的集合。
其他遞歸定義的數學對象包括階乘、函數(例如,遞歸關系)、集合(例如,康托爾三元集)和分形。
遞歸有各種更多的半開玩笑的定義; 參見遞歸幽默。
非正式定義
編輯遞歸是當過程的步驟之一涉及調用過程本身時過程所經歷的過程。 經過遞歸的過程被稱為“遞歸的”。
要理解遞歸,必須認識到過程和過程的運行之間的區別。 程序是基于一組規則的一組步驟,而程序的運行涉及實際遵循規則并執行這些步驟。
遞歸與過程規范中對其他過程執行的引用有關,但不相同。
當這樣定義過程時,這會立即產生無限循環的可能性; 如果在某些情況下跳過相關步驟以便完成過程,則遞歸只能在定義中正確使用。 遞歸有直接、間接和循環三種形式。 直接遞歸是函數 (A) 調用自身(A 引用 A); 間接遞歸發生在一個函數 (A) 調用 (B)、函數 (B) 調用函數 (C)、函數 (C) 調用 (D) 等時,直到鏈中的一個函數調用更早的函數。 當函數 (A) 和函數 (B) 相互調用時,就會發生循環遞歸。 如果在直接遞歸、間接遞歸或循環遞歸中出現死循環,則稱其為crock遞歸條件。 基本上有兩種方法可以防止 crock 遞歸,要么限制函數可以引用自身的次數,要么對函數調用的深度設置xxx限制,例如 如果深度限制為 50,則任何時候一個過程調用另一個過程時,計數器都會增加; 當它退出時,該計數器會減少。 一旦計數器達到限制(在本例中為 50),則不允許進一步的過程調用; 如果嘗試調用第 51 個函數,則操作終止。 使用遞歸限制只能防止 crock 遞歸; 除了停止 crock 遞歸之外,設置調用限制可能會產生副作用,即阻止執行深度嵌套但不是遞歸的合法復雜過程。
但是即使定義得當,遞歸過程對人類來說也不容易執行,因為它需要區分新的和舊的、部分執行的過程調用; 這需要對程序的各種同步實例的進展情況進行一些管理。 出于這個原因,遞歸定義在日常情況下非常少見。
語言
編輯語言學家諾姆·喬姆斯基 (Noam Chomsky) 和其他許多人認為,一種語言中的語法句子數量沒有上限,語法句子長度也沒有上限(超出實際限制,例如可以說出一個句子的時間) ), 可以解釋為自然語言遞歸的結果。
這可以根據句法類別(例如句子)的遞歸定義來理解。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/198271/