遞歸定義

遞歸定義是數理邏輯和計算機科學用到的一種定義方式，使用被定義對象的自身來為其下定義（簡單說就是自我複製的定義）。遞歸定義與歸納定義類似，但也有不同之處。遞歸定義中使用被定義對象自身來定義，而歸納定義是使用被定義對象的已經定義的部分來定義尚未定義的部分。不過，使用遞歸定義的函數或集合，它們的性質可以用數學歸納法，通過遞歸定義的內容來證明。

構造科赫曲線的前四個步驟，科赫曲線和很多分形一樣，是用遞歸定義的

定義方式

大部分的遞歸定義都由三個部分構成：基本情況的定義，遞歸法則和遞歸結束的情況。如果定義的對象是無限的，那麼可以省略第三個部分（遞歸結束的情況）。比如說，可以用遞歸定義的方式來定義如下的一個自然數集上的函數${\displaystyle f}$：

${\displaystyle f(0)=1}$

${\displaystyle \forall n>0,\,\,f(n)=n\times f(n-1).}$

這個定義在邏輯上是成立的，因為它首先定義了${\displaystyle f}$在最小的自然數0上的取值，接下來對每個大於零的自然數${\displaystyle n}$，只要重複有限多次定義的過程，最終就會回到對0的定義上。這樣定義出的函數${\displaystyle f}$就是階乘函數。

遞歸定義和循環定義的不同之處在於，後者不包括對基本情況的定義。比如定義建立在整數集上的函數${\displaystyle g}$：

${\displaystyle \forall n\in \mathbb {Z} ,\,\,g(n)=g(n-1)+1,}$

則我們永遠無法確定${\displaystyle g}$的取值，這便是循環定義。

遞歸定義的原理

基於遞歸定理，設${\displaystyle A}$是一個集合，並且設${\displaystyle a_{0}}$是${\displaystyle A}$的一個元素；如果有函數${\displaystyle \rho :f_{i}\mapsto a_{k}}$，為每個映射正整數集的非空子集至${\displaystyle A}$的函數${\displaystyle f_{i}}$，指派${\displaystyle A}$的一個元素${\displaystyle a_{k}}$，那麼存在一個唯一的函數${\displaystyle h:\mathbb {Z} _{+}\to A}$使得：

${\displaystyle {\begin{aligned}h(1)&=a_{0}\\h(i)&=\rho \left(h|_{\{1,2,\ldots ,i-1\}}\right){\text{ for }}i>1\end{aligned}}}$

這裡的${\displaystyle f\vert _{A}}$表示將${\displaystyle f}$限制於${\displaystyle A}$。

參考

• P. Aczel (1977), "An introduction to inductive definitions", Handbook of Mathematical Logic, J. Barwise (ed.), ISBN 0-444-86388-5
• James L. Hein (2009), Discrete Structures, Logic, and Computability. ISBN 0-7637-7206-2