遞歸函數是數論函數的一種，其定義域與值域都是自然數集，只是由于構作函數方法的不同而有別于其他的函數。最簡單又最基本的函數有三個：零函數O(x)=0(其值恒為0)，射影函數，后繼函數S(x)=x+1，它們合稱初始函數。要想由舊函數作出新函數，必須使用各種映射。
在數理邏輯和計算機科學中，遞歸函數或μ-遞歸函數是一類從自然數到自然數的函數，它是在某種直覺意義上是"可計算的"。事實上，在可計算性理論中證明了遞歸函數精確的是圖靈機的可計算函數。
?定理定義
數論函數的一種，其定義域與值域都是自然數集,只是由于構作函數方法的不同而有別于其他的函數。處處有定義的函數叫做全函數，未必處處有定義的函數叫做部分函數。最簡單又最基本的函數有三個：零函數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)。它們都滿足以下關系： 可以構造許多原始遞歸的配對函數。 遞歸函數也可以用來處理符號串。處理的辦法是對符號及符號串配以自然數。這方法是庫爾特·卡塞雷斯開始引進的，因此稱為哥德爾配數法。例如，在要處理的符號系統｛α1，α2，α3,…｝中，可以用奇數1，3，5，7，…作為α1,α2，α3，α4，…的配數，符號串以為其配數，其中Ps是第s個素數,nij是αij的配數。這種配數稱為哥德爾配數。有了哥德爾配數法，就可以用遞歸函數來描寫、處理有關符號串的謂詞了。 運用 (一) 目的：將1號和2號從A移到B 調用函數：hanoi(2,'A',?'C',?'B')。 在hanoi(2,'A',?'C',?'B')中遞歸調用如下： A-->C----河內(1,'A',?'B',?'C') A-->B----hanoi(1,'A',?'C',?'B') C-->B----hanoi(1,'C',?'A',?'B') (二) 目的：將3號從A移到C 調用函數：hanoi(1,'A',?'B',?'C') A-->C (三) 目的：將1號和2號從B移到C 調用函數：hanoi(2,'B',?'A',?'C') 在hanoi(2,'B',?'A',?'C')中遞歸遞歸如下： B-->A----河內(1,'B',?'C',?'A') B-->C----hanoi(1,'B',?'A',?'C') A-->C----hanoi(1,'A',?'B',?'C') 總共調用了7次函數， 只要hanoi()的第一個參數大于1，它就會在內部調用自身3次，“直到第一個參數＝1，然后調用printf()”。 hanoi(n,?...)調用hanoi(1,?...)的次數為2的n次方減去一。 pascal語言 【pascal語言】 函數?do(x:integer); begin if?x<=1?then?exit(0) else?if?x>1then?exit(do(x-1)+10) end; 【C++】 用遞歸法計算1+2+。。。N的值。 #include int?fn(int?i); void?main() { int?N; cout<<"\n輸入一個正整數:"; cin>>N; cout<<"\n?1+2+...+"< } //遞歸函數的定義 int?fn(int?i) { if(i==1) 回車鍵?1; else return?i+fn(i-1); } 正確寫出 如何快速正確的寫出遞歸函數？寫一個遞歸函數是非常程式化的東西，只要按照一定的規則來寫，就可以很容易地寫出遞歸函數。寫遞歸函數有三步： ①寫出迭代公式； ②確定遞歸終止條件； ③將①②翻譯成代碼。以求n！為例： ①寫出迭代公式：n！的迭代公式為 ②確定遞歸終止條件：1！＝1就是遞歸終止條件 ③將①②翻譯成代碼：將迭代公式等號右邊的式子寫入回車鍵語句中，即return?（fact（n-1））*n;long?fact（int?n）? {? if?（n==1）? return?1;? return?（fact（n-1））*n;? }? 下面再舉一個例子，希望能幫助大家進一步體會這一原則 寫一個函數，求：f（n）=陳氏定理+3+……+n的值 ①寫出迭代公式：迭代公式為?②確定遞歸終止條件：f（1）＝1就是遞歸終止條件 ③將①②翻譯成代碼：將迭代公式等號右邊的式子寫入return語句中，即return?（Sum（n-1））+n;? 將1！＝1翻譯成判斷語句：if（n==1）?return?1;? 按照先測試，后遞歸的原則寫出代碼。? long?Sum（int?n）?{? if?（n==1）? 回車鍵?1;? return?（Sum（n-1））+n;? } Oraclestart?with?connect?by?用法 oracle中?connect?by?prior?遞歸算法 Oracle中start?with...connect?by?prior子句用法?connect?by?是結構化查詢中用到的，其基本語法是： select?...?from?tablename?start?with?條件1 connect?by?條件2 where?條件3; 例： select?*?from?table start?with?org_id?=?'HBHqfWGWPy' connect?by?prior?org_id?=?parent_id; 簡單說來是將一個樹狀結構存儲在一張表里，比如一個表中存在兩個字段: org_id,parent_id那么通過表示每一條記錄的parent是誰，就可以形成一個樹狀結構。 用上述語法的查詢可以取得這棵樹的所有記錄。 其中： 條件1?是根結點的限定語句，當然可以放寬限定條件，以取得多個根結點，實際就是多棵樹。 條件2?是連接條件，其中用PRIOR表示上一條記錄，比如?CONNECT?BY?PRIOR?org_id?=?parent_id就是說上一條記錄的org_id?是本條記錄的parent_id，即本記錄的父親是上一條記錄。 條件3?是過濾條件，用于對返回的所有記錄進行過濾。 簡單介紹如下： 早掃描樹結構表時，需要依此訪問樹結構的每個節點，一個節點只能訪問一次，其訪問的步驟如下： 第一步：從根節點開始； 第二步：訪問該節點； 第三步：判斷該節點有無未被訪問的子節點，若有，則轉向它最左側的未被訪問的子節，并執行第二步，否則執行第四步； 第四步：若該節點為根節點，則訪問完畢，否則執行第五步； 第五步：返回到該節點的父節點，并執行第三步驟。 總之：掃描整個樹結構的過程也即是中序遍歷樹的過程。 參考資料 > Oracle遞歸函數.www.linuxidc.com.2015-11-16