對於某一函式f（x），其定義域是集合A，那么若對於A集合中的某一個值X0，其函式值f（x0）由f（f（x0））決定，那么就稱f（x）為遞進函式，又名遞歸函式，是電腦程式中比較常見的一種算法。
基本介紹
- 中文名：遞進函式
概述,定義,條件,計算,
概述
對於某一函式f（x），其定義域是集合A，那么若對於A集合中的某一個值X0，其函式值f（x0）由f（f（x0））決定，那么就稱f（x）為遞進函式，又名遞歸函式，是電腦程式中比較常見的一種算法。
定義
在數學上，關於遞歸函式的定義如下：對於某一函式f(x)，其定義域是集合A，那么若對於A集合中的某一個值X0，其函式值f(x0)由f(f(x0))決定，那么就稱f(x)為遞歸函式。
在程式語言中，把直接或間接地調用自身的函式稱為遞歸函式。函式的構建通常需要一個函式或者一個過程來完成。
在數理邏輯和計算機科學中，遞歸函式或μ-遞歸函式是一類從自然數到自然數的函式，它是在某種直覺意義上是"可計算的" 。事實上，在可計算性理論中證明了遞歸函式精確的是圖靈機的可計算函式。遞歸函式有關於原始遞歸函式，並且它們的歸納定義(見下)建造在原始遞歸函式之上。但是，不是所有遞歸函式都是原始遞歸函式 — 最著名的這種函式是阿克曼函式。
其他等價的函式類是λ-遞歸函式和馬爾可夫算法可計算的函式。
條件
一個含直接或間接調用本函式語句的函式被稱之為遞歸函式，它必須滿足以下兩個條件：
1） 在每一次調用自己時，必須是（在某種意義上）更接近於解；
2） 必須有一個終止處理或計算的準則。
例如：
梵塔的遞歸函式
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）；
}
}
計算
數論函式的一種，其定義域與值域都是自然數集，只是由於構作函式方法的不同而有別於其他的函式。處處有定義的函式叫做全函式，未必處處有定義的函式叫做部分函式。最簡單又最基本的函式有三個：零函式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）。另一個造新函式的運算元是原始遞歸式。
