子長縣

[拼音]：digui hanshu

[英文]：recursive function

數論函式的一種，其定義域與值域都是自然數集，只是由於構作函式方法的不同而有別於其他的函式。處處有定義的函式叫做全函式，未必處處有定義的函式叫做部分函式。最簡單又最基本的函式有三個:零函式O(x)=0(其值恆為0);射影函式

；後繼函式S(x)=x+1。它們合稱初始函式。要想由舊函式作出新函式，必須使用各種運算元。

代入（又名複合或疊置）是最簡單又最重要的造新函式的運算元，其一般形狀是：由一個m元函式ƒ與m個n元函式 g1，g2，…，gm 造成新函式 ƒ (g1(x1，x2，…，xn)，g2(x1，x2，…，xn)，…，gm(x1，x2，…，xn))，亦可記為ƒ(g1，g2，…，gm)(x1，x2，…，xn)。另一個造新函式的運算元是原始遞迴式。具有n個引數u1，u2，…，un的原始遞迴式為：

具有一個引數的原始遞迴式可簡寫為：

其特點是，不能由g、h兩函式直接計算新函式的一般值ƒ(u，x)，而只能依次計算ƒ(u，0)，ƒ(u，1)，ƒ(u，2)，…；但只要依次計算，必能把任何一個ƒ(u，x)值都算出來。換句話說只要g，h為全函式且可計算，則新函式f也是全函式且可計算。

由初始函數出發，經過有限次的代入與原始遞迴式而作出的函式叫做原始遞迴函式。由於初始函式顯然是全函式且可計算，故原始遞迴函式都是全函式且可計算。通常使用的數論函式全是原始遞迴函式，可見原始遞迴函式是包括很廣的。但是W.阿克曼證明了，可以作出一個可計算的全函式，它不是原始遞迴的。經過後人改進後，這個函式可寫為如下定義的阿克曼函式：

容易看出，這個函式是處處可計算的。任給m，n的值，如果m為0，可由第一式算出；如果m不為0而n為0，可由第二式化歸為求g(m，1)的值，這時第一變目減少了；如果m，n均不為0，根據第三式可先計算g(m，n-1)，設為α，再計算g(m-1，α)，前者第二變目減少（第一變目不變），後者第一變目減少。極易用歸納法證得，這樣一步一步地化歸，最後必然化歸到第一變目為0，從而可用第一式計算。所以這個函式是處處可計算的。此外又容易證明，對任何一個一元原始遞迴函式ƒ(x)，永遠可找出一數α使得ƒ(x)

另一個重要的造新函式的運算元是造逆函式的運算元，例如，由加法而造減法，由乘法造除法等。一般，設已有函式ƒ(u，x)，就x解方程ƒ(u，x)=t，可得x=g(u，t)。這時函式g叫做ƒ的逆函式。至於解一般方程ƒ(u，t，x)=0而得x＝g(u，t)可以看作求逆函式的推廣。解方程可以看作使用求根運算元。ƒ(u，t，x)=0的最小x根（如果有根的話），記為μx[ƒ(u，t，x)=0]。當方程沒有根時，則認為μx[ƒ(u，t，x)=0]沒有定義。可見，即使ƒ(u，t，x)處處有定義且可計算，但使用求根運算元後所得的函式μx[ƒ(u，t，x)=0]仍不是全函式，可為部分函式。但只要它有定義，那就必然可以計算。這運算元稱為μ運算元。如果ƒ(u，t，x)本身便是部分函式，則 μx[ƒ(u，t，x)=0]的意義是：當ƒ(u，t，n)可計算且其值為0，而x

原始遞迴函式類裡還有一個重要的子類稱為初等函式類，它是由非負整數與變元經過有窮次加、算術減（即｜α-b｜）、乘、算術除

、疊加Σ、疊乘П而得的函式組成的類。

波蘭人A.格熱高契克把原始遞迴函式類按定義的複雜程度來分類，稱為格熱高契克分層或波蘭分層。

要把遞迴函式應用於謂詞，首先要定義謂詞的特徵函式。謂詞R(x，y)的特徵函式是

稱謂詞R 是遞迴謂詞，若R 的特徵函式是遞迴函式；稱自然數子集A為遞迴集，若謂詞x∈A是遞迴謂詞。有了上述定義，就可以用遞迴函式來處理遞迴謂詞和遞迴集。為了處理N×N（其中N 為自然數集）的子集，就要建立配對函式，所謂配對函式通常是指由N×N 到N 的一個函式ƒ(x，y)與它的逆函式g1(z)，g2(z)。它們都滿足以下關係：