本節書摘來自華章出版社《算法基礎：打開算法之門》一書中的第2章，第2.4節，作者 ［美］托馬斯 h 科爾曼（thomas h cormen），更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視
利用遞歸技術，能将一個問題轉化為同一個樣子問題的求解過程。這是我最喜歡的經典的遞歸例子：計算n!（“n的階乘”），它被定義為如下，對于一個非負數n，當n=0時，n!=1且n!=n（n-1）（n-2）（n-3）…3•2•1(如果n≥1）。例如，5!=5•4•3•2•1=120。22觀察得（n-1）!=(n-1)(n-2)(n-3)…3•2•1,并且得n!=n•（n-1）!(對于n≥1)。針對n!這個問題，我們定義了“較小的”問題，也就是（n-1）!。我們能夠寫出一個遞歸程式來計算n!,具體如下:
第2步的表達方式過于啰嗦。我可以将其改寫為“otherwise,return n•factorial(n-1)”（否則，傳回nfactor2al(n-1)），即在一個更大的算術表達式中使用遞歸調用的傳回值。
對于遞歸，我們必須強調兩個特性。首先，必須有一個或多個基礎情況(base case)，它是指不用遞歸而直接計算出結果。第二，程式中的每個遞歸調用一定是通過一系列關于同一問題的子問題的求解而最終疊代到基礎情況。對于factorial程式，當n等于0時，基礎情況發生，并且每一個遞歸調用最終均會将n歸約到1。隻要初始時n是非負的，遞歸調用最終均會歸約到基礎情況。
證明遞歸算法工作流程的第一步可能讓人感覺過于簡單。證明的關鍵是每次遞歸調用均會産生正确的結果。隻要我們願意相信遞歸調用确實得到了正确結果，那麼證明正确性通常是容易的。如下是我們如何證明factorial程式傳回了正确的結果。很明顯，當n=0時，結果傳回1，1等價于n！。假定當n≥1時，factorial(n-1)這個遞歸調用傳回了正确的結果：它傳回了（n-1）!。該程式再用n乘以該值，是以計算出了n!這一結果，也就是最後要傳回的值。
下面舉一個程式，雖然它利用了正确的數學公式計算，但它不是基于子問題求解的遞歸調用。當n≥0時，确實有n!=（n+1）!/(n+1)。下列遞歸程式雖然利用了該數學公式，但是未能得出正确的結果（當n≥1時）：
如果要調用badfactorial(1)，那麼它會産生一個遞歸調用badfactorial(2)，該遞歸調用會産生一個遞歸調用badfactorial(3)，等等，這一系列遞歸調用均不會歸約到基礎情況（即n=0事件）。如果要用一種實際程式設計語言來實作該程式并且将該程式運作到一個真正的計算機上，那麼你會很快就能看到一條“棧溢出錯誤”的錯誤資訊。我們通常能将算法表示成一種遞歸風格的循環方式。如下是一個線性查找算法，它沒有使用标記，而是使用遞歸方式書寫的：
這裡，子問題是在a［i］～a［n］這個子數組中尋找x的問題。基礎情況發生在第1步中即當子數組本身是空時，也就是當i>n時。因為每執行一次第3步的遞歸調用，如果沒有第2步中的值傳回，i的值就會自增一，那麼最後i會大于n，此時我們會執行基礎情況。