直接調(diào)用自己或通過一系列的調(diào)用語句間接的調(diào)用自己的函數(shù)，稱為遞歸函數(shù)。
一、許多數(shù)學(xué)函數(shù)就是通過遞歸定義的，如：
階乘函數(shù)
1 若n=0 f(n) = n*f(n-1) 若n>0
2階Fibonacci函數(shù)
0 若n=0 Fib(n) = 1 若n=1 Fib(n-1)+Fib(n-2) 其他情況
Ackerman函數(shù)
n+1 m = 0 Ack(m,n)= Ack(m-1,1) n = 0 Ack(m-1,Ack(m,n-10） 其他情況
二、有些數(shù)據(jù)結(jié)構(gòu)，如二叉樹，廣義表等，由于結(jié)構(gòu)本身固有的遞歸特性，則它們的操作可遞歸的描述
三、有一類問題，雖然問題本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比迭代求解更簡單，如八皇后問題，漢諾塔問題
n階Hanoi塔問題：
假設(shè)有3個分別命名為X、Y、Z的塔座，在塔座X上插有n個直徑大小各不同、依小到大編號為1，2，...，n的圓盤?，F(xiàn)要求將X軸上的n個圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動時必須遵循下列規(guī)則：
1.每次只能移動一個圓盤
2.圓盤可以插在X 、Y、Z中的任一塔座上
3.任何時刻都不能將一個較大的圓盤壓在較小的圓盤上。
如何實(shí)現(xiàn)移動圓盤的操作呢?
當(dāng)n=1時，問題比較簡單，只要將編號為1的圓盤從塔座X直接移至塔座Z上即可；
當(dāng)n>1時，需利用塔座Y作為輔助塔，若能設(shè)法將壓在編號為n的圓盤之上的n-1個圓盤從塔座X移至塔座Y上，則可先將編號為n的圓盤從塔座X移至塔座Z上，然后再將塔座Y上的n-1個圓盤移至塔座Z上。
而如何將n-1個圓盤從一個塔座移至另一個塔座的問題是一個和原問題具有相同特征屬性的問題，只是問題的規(guī)模小1，因此可以用同樣的方法求解。
代碼：
local count = 0 -- 移動次數(shù)
function move (x, n,z)
count = count + 1
print(string.format("%d Move Disk %d from %s to %s", count, n, x, z))
end
function hanoi(n, x, y, z)
if n == 1 then
move(x,1,z) -- 編號為1的盤從x移到z
else
hanoi(n-1, x,z,y) -- x塔上編號為1至n-1的盤從x移到y(tǒng)，以z為輔助塔
move(x,n,z) -- 編號為n的盤從x移到z
hanoi(n-1, y,x,z) -- y塔上標(biāo)號為1至n-1的盤從y移到z，以x為輔助塔
end
end
hanoi(3,"A","B","C")
輸出
1 Move Disk 1 from A to C
2 Move Disk 2 from A to B
3 Move Disk 1 from C to B
4 Move Disk 3 from A to C
5 Move Disk 1 from B to A
6 Move Disk 2 from B to C
7 Move Disk 1 from A to C
總結(jié)：
一個遞歸函數(shù)的運(yùn)行過程類似與多個函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)與被調(diào)用函數(shù)是同一個函數(shù)，因此，和每次調(diào)用相關(guān)的一個重要概念是遞歸函數(shù)運(yùn)行的“層次”。
為了保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)需設(shè)立一個“遞歸工作?！弊鳛檎麄€遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲區(qū)。每一層遞歸所需信息構(gòu)成一個“工作記錄”，其中包括所有的實(shí)在參數(shù)，所有的局部變量以及上一層的返回地址。每進(jìn)入一層遞歸就產(chǎn)生一個新的工作記錄壓進(jìn)棧頂。每退出一層遞歸就從棧頂彈出一個工作記錄，則當(dāng)前執(zhí)行層的工作記錄必是遞歸工作棧棧頂?shù)墓ぷ饔涗?，這個記錄為”活動記錄“，指示活動記錄的棧頂指針稱為”當(dāng)前環(huán)境指針“。
