一、什么是遞歸?
當函數的定義中，其內部操作又直接或間接地出現對自身的調用，則稱這樣的程序嵌套定義為遞歸定義。
遞歸通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，從而大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合。用遞歸思想寫出的程序往往十分簡潔易懂。
二、遞歸的應用
用遞歸算法求x！
當x=0時，x！= 1
當x>0時， x！=x*(x-1)!
根據數學中的定義把求x！定義為求x*(x-1)!，其中求（x-1)!仍然用求x！的方法，需要定義一個求x！的函數，逐級調用此函數。
假設x=3時，3！=3*2*1=6，它執行的流程圖如圖：
編寫的程序如下：
#include <IOStream>
using namespace std;
int t;
int f(int);
int main()
{
int x;
cin >> x;
f(x);
cout << t <<endl;
return 0;
}
int f(int x)
{
if( x == 1)
t = 1;
else
{
f( x-1 );
t = t * x;
}
}
從上面這個例子中可以知道，遞歸算法的本質就是自己調用自己，用調用自己的方法去處理問題，可使解決問題變得簡潔明了。
1、遞歸程序在執行過程中，一般具有如下模式：
① 將調用程序的返回地址、相應地調用前的變量都保存在系統堆棧中，
② 執行被調用的函數；
③ 若滿足退出遞歸的條件，則退出，并從棧頂上彈回返回地址，取回保存起來的變量值，繼續沿著返回地址向下執行程序；
④ 否則繼續遞歸調用，只是遞歸調用的參數發生變化：增加一個量或減少一個量，重復執行直到遞歸調用結束。
2、能夠用遞歸算法解決的問題，一般滿足如下要求：
① 需要求解的問題可以化為子問題求解，其子問題的求解方法與原問題相同，只是規模上的增加或減少
② 遞歸調用的次數是有限的，必須有遞歸結束的條件。
一個經典的益智游戲——漢諾塔，就是典型的遞歸算法：
有A、B、C三個塔座和n個大小不一樣的圓盤子，需要把A、B、C三個塔座上的盤子利用中間B座，把所有盤子從A盤移動到C盤，規則是每次只允許移動一個盤子，并且在移動過程中，3個座上的盤子始終保持大盤在下，小盤在下。
分析如下：
當盤子數n=1時，只需移動一次：A--->C。
當盤子數n=2時，需要移動三次：A--->B，A--->C，B--->C。
當盤子數n=3時，需要移動7次：A--->C，A--->B，C--->B，A--->C，B--->A，B--->C，A--->C。
由以上分析可知：如果盤子數為n時，則移動的次數為2n-1.
那么如何編寫一個盤子數為n的程序呢？我們利用遞歸的算法來設計程序，你會發現，要把A座上的n個盤子以B座為中轉移動到C座，可以分為以下3個步驟來完成：
1、將A座上的n-1個盤子，以C座為中轉，移到B座上。
2、把A座上最低下的一個盤子移到C座上。
3、將B座上n-1個盤子，以A座為中轉，移到C座上。
可以發現步驟1和3是和原問題本質相同的子問題（規模數量少了1），不停地遞歸下去，直到當子問題的規模數為1時，只需執行第1個步驟。
這是盤子n=3時，遞歸算法運行的過程：
圖中的數字順序表示程序運行的順序。
程序代碼可以看我主頁里分享的視頻。
