遞歸

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

遞歸英文recursion)係指一件物件用自己嚟定義佢自己,喺數學(包括電腦科學)同語言學經常會用到。

[編輯]

數學[編輯]

數學好多時都會用到遞歸。例如,階乘可以咁定義:

,當中

當中 n > 0 嘅時候佢就係用自己定義自己。

程式編寫遞歸概念,基本同數學一致。例如,如果用 Scheme(一種 Lisp),上面嘅例子可以粗略咁直接譯做

(define (factorial n)
        (if (= n 0)
            1
            (* n (factorial (- n 1)))))

不過,因為編程嘅遞歸牽涉到有限嘅堆叠資源,真嘅程式唔可以寫得咁求其,因為 冇譯到,唔譯呢句可以導致無限遞歸,後果可以好嚴重。

語言學[編輯]

語言學都會用到遞歸,例如喺描述一個語言嘅文法嘅時候,名詞短語可能可以咁樣粗略描述:

NP → N
NP → Adj NP

第二個情形(NP → Adj NP,即係 「名詞短語可以係一個形容詞加一個名詞短語」)亦都就係用自己定義自己。當然,呢個係一個假想嘅例子,真嘅語言唔會咁簡單。

呢種遞歸喺電腦科學都有用到,例如喺寫編譯器嘅時候,編程語言嘅語法都係用呢種文法來定義;實作嘅時候可能會用到編程嘅遞歸。

睇埋[編輯]