程式語言中，函式Func(Type a,……)直接或間接調用函式本身，則該函式稱為遞歸函式。遞歸函式不能定義為內聯函式。
在數學上，關於遞歸函式的定義如下：對於某一函式f(x)，其定義域是集合A，那么若對於A集合中的某一個值X0，其函式值f(x0)由f(f(x0))決定，那么就稱f(x)為遞歸函式。
基本介紹
定義,介紹,一個直接的例子,條件,計算,例子,
定義
一種計算過程，如果其中每一步都要用到前一步或前幾步的結果，稱為遞歸的。用遞歸過程定義的函式，稱為遞歸函式，例如連加、連乘及階乘等。凡是遞歸的函式，都是可計算的，即能行的。
古典遞歸函式，是一種定義在自然數集合上的函式，它的未知值往往要通過有限次運算回歸到已知值來求出，故稱為“遞歸”。它是古典遞歸函式論的研究對象。
介紹
在數理邏輯和計算機科學中，遞歸函式或μ-遞歸函式是一類從自然數到自然數的函式，它是在某種直覺意義上是"可計算的" 。事實上，在可計算性理論中證明了遞歸函式精確的是圖靈機的可計算函式。遞歸函式有關於原始遞歸函式，並且它們的歸納定義(見下)建造在原始遞歸函式之上。但是，不是所有遞歸函式都是原始遞歸函式 — 最著名的這種函式是阿克曼函式。
其他等價的函式類是λ-遞歸函式和馬爾可夫算法可計算的函式。
一個直接的例子
//代碼1void func(){//...if(...)func();else//...}條件
一個含直接或間接調用本函式語句的函式被稱之為遞歸函式，在上面的例子中能夠看出，它必須滿足以下兩個條件：
1） 在每一次調用自己時，必須是（在某種意義上）更接近於解；
2） 必須有一個終止處理或計算的準則。
例如：
梵塔的遞歸函式
//Cvoid 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;elsereturn n * Factorial(n-1)}計算
函式的概念是一個很一般的概念。在定義函式時，不一定要具體給出通過自變數求函式值的方法。因此，可將函式分成兩類，一類是所謂能行可計算函式，另一類是非能行可計算的函式。這前一種函式無論在理論上或在實際上都是非常重要的，因此人們便試圖給它們以精確的數學刻畫。遞歸函式便是許多這種刻畫中的一種。
我們以下考慮的函式都是從自然數到自然數的函式。
我們先定義幾個初等函式
(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代碼格式，實際為Pascalfunctiondo(x:integer);beginifx<=1thenexit(0)elseifx>1thenexit(do(x-1)+10)end;
