遞歸

遞歸（粵拼：dai6 gwai1 | 英文：recursion）係指一件物件用自己嚟定義佢自己，喺數學（包括電腦科學）同語言學經常會用到。

例

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

n!={\begin{cases}1\qquad &{\text{如}}\,\,{\text{果}}\,\,\,n=0\\n\times (n-1)!&{\text{如}}\,\,{\text{果}}\,\,\,n>0\\\end{cases}}\qquad

，當中

n\in \mathbf {Z} ,n\geq 0

。

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

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

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

不過，因為編程嘅遞歸牽涉到有限嘅堆叠資源，真嘅程式唔可以寫得咁求其，因為 $n\in \mathbf {Z} ,n\geq 0$ 冇譯到，唔譯呢句可以導致無限遞歸，後果可以好嚴重。

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

NP → N

NP → Adj NP

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

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