遞歸
遞歸一個函數直接或間接調用自己的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解。遞歸要滿足3個條件：一是遞歸必須得有一個明確的中止條件，要不然就很可能陷入死遞歸；二是遞歸函數所處理數據(或問題)的規模必須在遞減，n個問題的解決依賴於n-1個問題的解決；三是這個轉化必須是可解的。
函數的調用機制
當在一個函數的運行期間調用另一個函數時，在運行被調函數之前，系統需要完成三件事：
a).將所有的實際參數，返回地址(下一條語句的地址)等信息傳遞給被調函數保存；
b).為被調函數的局部變量(也包括形參)分配存儲空間；
c).將控制權限轉移到被調函數的入口；
從被調函數返回主調函數之前，系統也要完成三件事：
a>.保存被調函數的返回的結果；
b>.釋放被調函數所占的存儲空間；
c>.依照被調函數保存的返回地址將控制權限轉移到調用函數。
當多個函數相互調用時，按照“後調用先返回”的原則，上述函數之間信息傳遞和控制權限轉移必須借助
“棧”來實現，即系統將整個程序運行時所需的數據空間安排在一個棧中，每當調用一個函數時，就在棧
頂分配一塊存儲區，進行壓棧操作；每當一個函數退出時，就釋放它的存儲區，進行出棧操作，當前運行
的函數永遠都在棧頂位置！
在計算機看來，A函數調用A函數和A函數調用B函數本質上是一樣的。每調用一個函數，進行壓棧操作；每
當函數退出時，就釋放它的存儲區就行出棧操作，當前運行的函數永遠都在棧頂位置。
循環和遞歸的比較
遞歸優點：易於理解(問題規模原來可以轉化為范圍越來越小的問題)
遞歸缺點：速度慢(由函數調用機制決定，每次遞歸都得調自己)，存儲空間大(浪費空間很大)
循環優點：速度相對快 ，存儲空間小(浪費空間很小)
循環缺點：不易理解(很多算法需要我們一個一個去推)
所有的循環都可以用遞歸實現，但所有的遞歸不一定可以用循環實現。
漢諾塔問題
問題描述：如何把A柱(第一根柱子)上面的n個盤子借助B柱(第二根柱子)移到C柱(第三根柱子)上？，且一次只能移動一個盤子，移動過程中小盤子必須始終放在大盤子上面(最下面的盤子編號最大)。
偽算法：1.當A柱子上只有1個盤子時，可直接將A柱上的盤子移到C柱
2.當A柱子上的盤子為n個時(n>1)，此時可利用遞歸的思想分3步解決：
1).將A柱上的n-1個盤子借助C柱移到B柱；
2).將 A柱上的第n個盤子直接移到C柱上;
3).將B柱上的n-1個盤子借助A柱移到C柱上；
遞歸算法實現(規定柱子上至少有一個盤子)：
#include<stdio.h>
void Hanoitower(int n,char A,char B,char C)
{
if(1==n)
{
printf("將編號為%d的盤子從%c柱移到%c柱上\n",n,A,C);
}
else
{
Hanoitower(n-1,A,C,B);
printf("將編號為%d的盤子從%c柱移到%c柱上\n",n-1,A,C);
Hanoitower(n-1,B,A,C);
}
}
int main()
{
int n;
printf("請輸入盤子的個數：");
scanf("%d",&n);
Hanoitower(n,'A','B','C');
return 0;
}
#include<stdio.h>
void Hanoitower(int n,char A,char B,char C)
{
if(1==n)
{
printf("將編號為%d的盤子從%c柱移到%c柱上\n",n,A,C);
}
else
{
Hanoitower(n-1,A,C,B);
printf("將編號為%d的盤子從%c柱移到%c柱上\n",n-1,A,C);
Hanoitower(n-1,B,A,C);
}
}
int main()
{
int n;
printf("請輸入盤子的個數：");
scanf("%d",&n);
Hanoitower(n,'A','B','C');
return 0;
}
由盤子轉移的次數可以推算出：漢諾塔的復雜度是2的n次方-1。
結束語
遞歸在很多地方用到，如樹、圖都是以遞歸的方式定義的。遞歸為我們解決復雜問題提供了方面(但這基本上是數學上的問題，所以理解要它的邏輯有時會很難)。學線性結構(數組、鏈表及其應用的棧、隊列等)、遞歸及它們思想主要是為以後方面我們能將非線性問題轉化為線性問題，進而通過線性結構的方法及思想來解決非線性結構問題。
