棧的一個(gè)重要應(yīng)用是在程序設(shè)計(jì)語言中實(shí)現(xiàn)遞歸。所謂遞歸，是指如果一個(gè)對(duì)象部分地包括它自己，或用它自己給自己定義，則稱這個(gè)對(duì)象是遞歸的，或定義為在一個(gè)過程中直接或間接地調(diào)用自己，則稱這個(gè)過程是遞歸的。在調(diào)用一個(gè)函數(shù)（程序）的過程中又直接或間接地調(diào)用該函數(shù)（程序）本身，稱為函數(shù)的遞歸調(diào)用。一個(gè)遞歸的求解問題必然包含終止遞歸的條件，當(dāng)滿足一定條件時(shí)就終止向下遞歸，從而使問題得到解決。描述遞歸調(diào)用過程的算法稱為遞歸算法。在遞歸算法中，需要根據(jù)遞歸條件直接或間接地調(diào)用算法本身，當(dāng)滿足終止條件時(shí)結(jié)束遞歸調(diào)用。

現(xiàn)實(shí)中有許多實(shí)際問題采用遞歸方法來解決，使用遞歸的方法編寫程序?qū)⑹乖S多復(fù)雜的問題大大簡化。例如計(jì)算求n的階乘問題，可以利用階乘的遞推公式n!=n*(n-1)!，對(duì)該問題進(jìn)行分解，把計(jì)算n的階乘問題化為等式右邊涉及規(guī)模較小的同類問題(n-1)的階乘的計(jì)算。

例用遞歸函數(shù)求解正整數(shù)n的階乘（n!）

設(shè)f(n)=n!，則遞歸函數(shù)f(n)可表示為：

此處n=0為遞歸終止條件，使函數(shù)返回1；當(dāng)n>0時(shí)實(shí)現(xiàn)遞歸調(diào)用，由n的值乘以f(n-1)的返回值求出f(n)的值。

上述遞歸函數(shù)用c語言描述為：

可見，遞歸算法設(shè)計(jì)的原則是用自身的簡單情況來定義自身，使其一步比一步更簡單，直至終止條件。設(shè)計(jì)遞歸算法的方法是：

（1）尋找遞歸的通式，將規(guī)模較大的原問題分解為規(guī)模較小、但具有類似于原問題特性的子問題。即較大的問題遞歸地用較小的子問題來描述，解原問題的方法同樣可用來解這些子問題（例如n!=n*(n-1)!）。

（2）設(shè)置遞歸出口，確定遞歸終止條件（例如求解n!時(shí)，當(dāng)n=0時(shí)，f(0)=1）。

上述求階乘的遞歸函數(shù)中，假設(shè)n=4，遞歸函數(shù)f(4)的調(diào)用和返回過程如圖3-4所示。

從圖3-4可知，求解f(4)的值分為遞歸和返回求解兩個(gè)階段，在遞歸階段，每一次調(diào)用f(n)函數(shù)時(shí)，并不是立即得到f(n)的值，而是一次一次地進(jìn)行遞歸調(diào)用，即求f(4)需遞歸調(diào)用f(3)，而f(3)無法求得，進(jìn)而需要調(diào)用f(2)，依次類推，直到f(0)有確定值時(shí)，遞歸不再進(jìn)行，然后開始返回求解階段。遞歸終止時(shí)，f(0)=1，由此可求出1*f(0)=1為f(1)的返回值，再由f(1)的值求出2*f(1)=2*1=2，作為f(2)的返回值。依次返回求解，最后遞推出f(4)=24。

遞歸函數(shù)調(diào)用時(shí)，是按照“后調(diào)用先返回”的原則處理調(diào)用過程，如上述求階乘的遞歸函數(shù)調(diào)用，最后調(diào)用的是f(0)，因而最先返回f(0)的值。因此執(zhí)行遞歸函數(shù)是通過具有后進(jìn)先出性質(zhì)的棧來實(shí)現(xiàn)的。系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)就為它在棧頂分配一個(gè)存儲(chǔ)空間，而每當(dāng)從一個(gè)函數(shù)退出時(shí)，就釋放它的存儲(chǔ)區(qū)。