'C語言：數據結構-棧與遞歸'

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

現實中有許多實際問題採用遞歸方法來解決，使用遞歸的方法編寫程序將使許多複雜的問題大大簡化。例如計算求n的階乘問題，可以利用階乘的遞推公式n!=n*(n-1)!，對該問題進行分解，把計算n的階乘問題化為等式右邊涉及規模較小的同類問題(n-1)的階乘的計算。

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

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

此處n=0為遞歸終止條件，使函數返回1；當n>0時實現遞歸調用，由n的值乘以f(n-1)的返回值求出f(n)的值。

上述遞歸函數用c語言描述為：

\tint f(int n)
\t{
\t if(n==0) return 1;
\t else return n*f(n-1);
\t}

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

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

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

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

求解f（4）的過程

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

遞歸函數調用時，是按照“後調用先返回”的原則處理調用過程，如上述求階乘的遞歸函數調用，最後調用的是f(0)，因而最先返回f(0)的值。因此執行遞歸函數是通過具有後進先出性質的棧來實現的。系統將整個程序運行時所需的數據空間安排在一個棧中，每當調用一個函數時就為它在棧頂分配一個存儲空間，而每當從一個函數退出時，就釋放它的存儲區。