遞歸

數學

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

${\displaystyle n!={\begin{cases}1\qquad &{\text{如}}\,\,{\text{果}}\,\,\,n=0\\n\times (n-1)!&{\text{如}}\,\,{\text{果}}\,\,\,n>0\\\end{cases}}\qquad }$ ，當中 ${\displaystyle n\in \mathbf {Z} ,n\geq 0}$ 。

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

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

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

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

語言學

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

NP → N
NP → Adj NP

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

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

• 電腦科學上講嘅遞歸
• 碎形
• 句子

呢篇同邏輯相關係楔位文。歡迎幫維基百科擴寫佢。 睇 • 論 • 改 • 歷