本人學(xué)c++，c的語法已經(jīng)淡忘了，但是遞歸不管什么語言都是一個(gè)原理
創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比溫宿網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式溫宿網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋溫宿地區(qū)。費(fèi)用合理售后完善，十載實(shí)體公司更值得信賴。
其實(shí)簡單一點(diǎn)來說就像數(shù)學(xué)里面的數(shù)列的通項(xiàng)公式：
例如一個(gè)數(shù)列是2，4，6，8，10......
很容易就可以得到通項(xiàng)公式是a[n]=2*n n是大于0的整數(shù)
你肯定學(xué)過這個(gè)數(shù)列的另外一種表示方式就是： a[1]=2, a[n]=a[n-1]+2 n是大于1的整數(shù)
其實(shí)這就是一個(gè)遞歸的形式，只要你知道初始項(xiàng)的值，未知項(xiàng)和前幾項(xiàng)之間的關(guān)系就可以知道整個(gè)數(shù)列。
程序例子：比如你要得到第x項(xiàng)的值
普通循環(huán)：
for(int i=1; i=n; i++)
if (i == x)
cout 2*i; /*cout 相當(dāng)于 c里面的printf,就是輸出.*/
遞歸：
int a(int x) {
if (x = 1)
return 2; /* 第一項(xiàng)那肯定是2了，這個(gè)也是遞歸的終止條件！ */
else return a(x-1)+2; /* 函數(shù)自身調(diào)用自身是遞歸的一個(gè)特色 */
比如x=4,那么用數(shù)學(xué)表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2
其實(shí)遞歸方法最接近自然，也是最好思考的一個(gè)方法，難點(diǎn)就是把對(duì)象建模成遞歸形式，但是好多問題本身就是以遞歸形式出現(xiàn)的。
普通遞歸就是數(shù)據(jù)結(jié)構(gòu)上的堆棧，先進(jìn)后出。
例如上面x=4,把a(bǔ)(4)放入棧底，然后放入a(3),然后a(2),a(1),a(1)的值已知，出棧，a(1)=2,a(2)出棧a(2)=a(1)+2=2+2=4,a(3)出棧a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出棧a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8
再比如樓上的階乘例子，當(dāng)n=0 或 1時(shí),0!=1,1!=1,這個(gè)是階乘的初始值，也是遞歸的終止條件。然后我們知道n!=n*(n-1)!,當(dāng)n1時(shí),這樣我們又有了遞歸形式，又可以以遞歸算法設(shè)計(jì)程序了。（樓上已給出譚老的程序，我就不寫了）。
我給出一種優(yōu)化的遞歸算法---尾遞歸。
從我給出的第一算法可以看出，先進(jìn)棧再出棧，遞歸的效率是很低的。速度上完全比不上迭代（循環(huán)）。但是尾遞歸引入了一個(gè)新的函數(shù)參數(shù)，用這個(gè)新的函數(shù)參數(shù)來記錄中間值.
普通遞歸階乘fac(x),就1個(gè)x而已，尾遞歸用2個(gè)參數(shù)fac(x,y),y存放階乘值。
所以譚老的程序就變成
// zysable's tail recursive algorithm of factorial.
int fac(int x, int y) {
if (x == 1)
return y;
else return fac(x-1, y*x);}
int ff(int x) {
if (x == 0)
return 1;
else return fac(x,1);}
對(duì)于這個(gè)程序我們先看函數(shù)ff，函數(shù)ff其實(shí)是對(duì)fac的一個(gè)封裝函數(shù)，純粹是為了輸入方便設(shè)計(jì)的，通過調(diào)用ff(x)來調(diào)用fac(x,1),這里常數(shù)1就是當(dāng)x=1的時(shí)候階乘值了，我通過走一遍當(dāng)x=3時(shí)的值即為3!來說明一下。
首先ff(3),x!=0,執(zhí)行fac(3,1).第一次調(diào)用fac，x=3,y=1,x!=1,調(diào)用fac(x-1,y*x),新的x=2,y=3*1=3,這里可以看到，y已經(jīng)累計(jì)了一次階乘值了，然后x還是!=1,繼續(xù)第三次調(diào)用fac(x-1,y*x),新的x=1,y=2*3=6,然后x=1了，返回y的值是6，也就是3！.你會(huì)發(fā)現(xiàn)這個(gè)遞歸更類似于迭代了。事實(shí)上我們用了y記錄了普通遞歸時(shí)候，出棧的乘積，所以減少了出棧后的步驟，而且現(xiàn)在世界上很多程序員都在倡議用尾遞歸取消循環(huán)，因?yàn)橛行┰诤芏嘟忉屍魃衔策f歸比迭代稍微效率一點(diǎn).
基本所有普通遞歸的問題都可以用尾遞歸來解決。
一個(gè)問題以遞歸來解決重要的是你能抽象出問題的遞歸公式，只要遞歸公式有了，你就可以放心大膽的在程序中使用，另外一個(gè)重點(diǎn)就是遞歸的終止條件；
其實(shí)這個(gè)終止條件也是包含在遞歸公式里面的，就是初始值的定義。英文叫define initial value. 用普通遞歸的時(shí)候不要刻意讓自己去人工追蹤程序，查看運(yùn)行過程，有些時(shí)候你會(huì)發(fā)現(xiàn)你越看越不明白，只要遞歸公式轉(zhuǎn)化成程序語言正確了，結(jié)果必然是正確的。學(xué)遞歸的初學(xué)者總是想用追蹤程序運(yùn)行來讓自己來了解遞歸，結(jié)果越弄越糊涂。
如果想很清楚的了解遞歸，有種計(jì)算機(jī)語言叫scheme,完全遞歸的語言，因?yàn)闆]有循環(huán)語句和賦值語句。但是國內(nèi)人知道的很少，大部分知道是的lisp。
好了，就給你說到這里了，希望你能學(xué)好遞歸。
PS:遞歸不要濫用，否則程序極其無效率，要用也用尾遞歸。by 一名在美國的中國程序員zysable。
第一級(jí)遞歸：n=483，i=n/10=48≠0
注意此時(shí)先遞歸調(diào)用convert(48)，待遞歸返回再輸出當(dāng)前n的個(gè)位數(shù)字n%10=3
第二級(jí)遞歸：n=48，i=n/10=4≠0
此時(shí)繼續(xù)遞歸調(diào)用convert(4)，待遞歸返回再輸出當(dāng)前n的個(gè)位數(shù)字n%10=8
第三級(jí)遞歸：n=4，i=n/10=0
此時(shí)遞歸終止，先輸出當(dāng)前n的個(gè)位數(shù)字n%10=4
再返回上一級(jí)遞歸輸出8，最后返回第一級(jí)遞歸輸出3
因此最終輸出為：4 8 3
遞歸函數(shù)：
編程語言中，函數(shù)Func(Type a,……)直接或間接調(diào)用函數(shù)本身，則該函數(shù)稱為遞歸函數(shù)。遞歸函數(shù)不能定義為內(nèi)聯(lián)函數(shù)。
在數(shù)學(xué)上，關(guān)于遞歸函數(shù)的定義如下：對(duì)于某一函數(shù)f(x)，其定義域是集合A，那么若對(duì)于A集合中的某一個(gè)值X0，其函數(shù)值f(x0)由f(f(x0))決定，那么就稱f(x)為遞歸函數(shù)。
函數(shù)介紹：
在數(shù)理邏輯和計(jì)算機(jī)科學(xué)中，遞歸函數(shù)或μ-遞歸函數(shù)是一類從自然數(shù)到自然數(shù)的函數(shù)，它是在某種直覺意義上是"可計(jì)算的" 。事實(shí)上，在可計(jì)算性理論中證明了遞歸函數(shù)精確的是圖靈機(jī)的可計(jì)算函數(shù)。遞歸函數(shù)有關(guān)于原始遞歸函數(shù)，并且它們的歸納定義(見下)建造在原始遞歸函數(shù)之上。但是，不是所有遞歸函數(shù)都是原始遞歸函數(shù) — 最著名的這種函數(shù)是阿克曼函數(shù)。
其他等價(jià)的函數(shù)類是λ-遞歸函數(shù)和馬爾可夫算法可計(jì)算的函數(shù)。
例子：
//代碼1
void func()
{
//...
if(...)
func();
else
//...
}
條件：
一個(gè)含直接或間接調(diào)用本函數(shù)語句的函數(shù)被稱之為遞歸函數(shù)，在上面的例子中能夠看出，它必須滿足以下兩個(gè)條件：
1） 在每一次調(diào)用自己時(shí)，必須是（在某種意義上）更接近于解；
2） 必須有一個(gè)終止處理或計(jì)算的準(zhǔn)則。
梵塔的遞歸函數(shù)：
//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);
}
}
可以使用遞歸來實(shí)現(xiàn)對(duì)表達(dá)式 `1-2+3-4……-100` 求和。遞歸算法的基本思路是將一個(gè)大問題分解成多個(gè)相同或類似的小問題，然后將這些小問題按照一定規(guī)律組合成大問題的解。對(duì)于這道題，可以將表達(dá)式 `1-2+3-4……-100` 分解成兩個(gè)子問題：
- 1-2+3-4……-98-99+100
- -99+100
然后對(duì)每個(gè)子問題遞歸求解即可。
具體的遞歸算法可以這樣實(shí)現(xiàn)：
```c
int sum = 0; // 定義變量 sum 存儲(chǔ)表達(dá)式的和
int calc(int n) { // 定義遞歸函數(shù) calc，n 表示當(dāng)前計(jì)算的數(shù)值
if (n == 1) {
return 1; // 表達(dá)式中只有一個(gè)數(shù)值 1，直接返回 1
}
if (n % 2 == 0) {
return -n + calc(n - 1); // 當(dāng)前數(shù)值為偶數(shù)，則加上負(fù)號(hào)
} else {
return n + calc(n - 1); // 當(dāng)前數(shù)值為奇數(shù)，則加上正號(hào)
}
}
int main() {
sum = calc(100); // 計(jì)算表達(dá)式的總和
printf("表達(dá)式的和為：%d
", sum);
return 0;
}
```
運(yùn)行結(jié)果為：
```
表達(dá)式的和為：-50
```
其中，`calc(n)` 函數(shù)用于遞歸計(jì)算表達(dá)式前 n 個(gè)數(shù)的和。如果當(dāng)前 n 為奇數(shù)，則返回 `n + calc(n - 1)`；如果當(dāng)前 n 為偶數(shù)，則返回 `-n + calc(n - 1)`。最終的表達(dá)式和存儲(chǔ)在變量 `sum` 中，通過 `printf` 函數(shù)輸出。
需要注意的是，在實(shí)際的應(yīng)用中，遞歸算法往往會(huì)帶來額外的開銷、增加內(nèi)存負(fù)荷，所以需要根據(jù)具體問題的規(guī)模和復(fù)雜度來選擇算法。對(duì)于本題，迭代算法也可以輕松實(shí)現(xiàn)，效率更高。
重慶分公司
重慶分公司
