-
遞歸函數
鎖定
編程語言中，函數Func(Type a,……)直接或間接調用函數本身，則該函數稱為遞歸函數。遞歸函數不能定義為內聯函數。
在數學上，關於遞歸函數的定義如下：對於某一函數f(x)，其定義域是集合A，那麼若對於A集合中的某一個值X0，其函數值f(x0)由f(f(x0))決定，那麼就稱f(x)為遞歸函數。
遞歸函數定義
遞歸函數基本介紹
在數理邏輯和計算機科學中，遞歸函數或μ-遞歸函數是一類從自然數到自然數的函數，它是在某種直覺意義上是"可計算的" 。事實上，在可計算性理論中證明了遞歸函數精確的是圖靈機的可計算函數。遞歸函數有關於原始遞歸函數，並且它們的歸納定義(見下)建造在原始遞歸函數之上。但是，不是所有遞歸函數都是原始遞歸函數 — 最著名的這種函數是阿克曼函數。
其他等價的函數類是λ-遞歸函數和馬爾可夫算法可計算的函數。
遞歸函數一個直接的例子
//代碼1
void func()
{
//...
if(...)
func();
else
//...
}遞歸函數條件
一個含直接或間接調用本函數語句的函數被稱之為遞歸函數，在上面的例子中能夠看出，它必須滿足以下兩個條件：
1） 在每一次調用自己時，必須是（在某種意義上）更接近於解；
2） 必須有一個終止處理或計算的準則。
例如：
梵塔的遞歸函數
//C
void hanoi(int n,char x,char y,char z)
{
if(n==1)
move(x,1,z);
else
{
hanoi(n-1,x,z,y);
move(x,n,z);
hanoi(n-1,y,x,z);
}
}
階乘的遞歸函數，公式如下：
//C++
int Factorial(int n)
{
if(n==0||n==1)
return 1;
else
return n * Factorial(n-1)
}遞歸函數計算
函數的概念是一個很一般的概念。在定義函數時，不一定要具體給出通過自變量求函數值的方法。因此，可將函數分成兩類，一類是所謂能行可計算函數，另一類是非能行可計算的函數。這前一種函數無論在理論上或在實際上都是非常重要的，因此人們便試圖給它們以精確的數學刻畫。遞歸函數便是許多這種刻畫中的一種
[2]
。
我們以下考慮的函數都是從自然數到自然數的函數。
我們先定義幾個初等函數
(1)零函數 Z(x)=0;
(2)後繼函數 S(x)=x+1;
(3)廣義幺函數 U1n(x1，…xn)=xi;
顯然，上面這些函數都是能行可計算的。
再介紹幾個將函數變換為函數的算子。
(1)複合算子 設f是n元函數，g1…gn是m元函數，複合算子將f，g1…gn變換成為如下的m元函數h：
h(x1…xm)=f1g1(x1，…xm)，…gn(x1，…xm))
(2)遞歸算子 設f是n元函數 (≥0)，g是n+2元函數，遞歸算子將f，g變換成滿足下列條件的h+1元函數h：
h(x1，…，xn，0)=f(x1，…xn)
h(x1，…xn，y+1)=g(x1，…xn，y，h(x1，…xn))
(3)μ一算子，設f是n+1元函數，如果存在y，使f(x1，…xn，y)=0，我們以μyf(x1…xny)表示這樣的y中的最小者，如果使f(x1…xny)=0的y不存在，我們説μyf(x1，…xny)無定義。μ-算子將n+1元函數f變換成下面的幾元函數h
h(x1，…xn)=μyf(x1…xny)
注意，μ算子可以將一個全函數變換成一個部分函數(即在自然數的某個子集上有定義的函數)。
可以看出，上述所有算子都是將能行可計算函數變換為能行可計算函數。
所謂遞歸函數類便是包含零函數、廣義幺函數，並在複合算子、遞歸算子，μ-算子下封閒的最小函數類。
容易相信，任何遞歸函數都是能行可計算的。反過來，是否存在直觀上能行可計算的，但不是遞歸的函數呢?人們直到現在還沒有發現這樣的函數。相反，人們證明了，現已遇到的直觀上能行可計算的函數都是遞歸函數。進一步，人們還證明了，遞歸函數類與其他的一些刻畫能行可計算函數的方法產生的函數類是完全一致的，這些事實促使車爾赤(Church)提出了他的著名的論點：
遞歸函數類與直觀能行可計算函數類是重合的。
這個論點已被大多數遞歸論學者所接受。
遞歸函數例子
【pascal語言】
//使用VB代碼格式，實際為Pascal functiondo(x:integer); begin ifx<=1thenexit(0) elseifx>1thenexit(do(x-1)+10) end;
