對於新手來說，覺得遞迴難以理解是很正常的事情，對於大部分人來說，只要下功夫認真學習，還是可以學會的，如果實在學不會，那麼只能遺憾的告訴你，你並不適合學程式設計。

先看一個現實中的例子，假設你被鎖到家門外，你在樓下的信箱裡面放了一把備用鑰匙，於是你要信箱去取，卻發現信箱的鑰匙在物業那裡，為了開啟信箱，你來到物業辦公室，工作人員卻告訴你鑰匙在保險櫃裡，保險櫃的鑰匙在經理手裡，所以你又找到經理拿到保險櫃的鑰匙，然後開啟保險櫃拿到信箱的鑰匙，再開啟信箱拿到房子鑰匙，最後開啟房門。注意這裡有兩個過程，一個是展開，展開到底之後，開始反向求值。

遞迴不是C語言的專利，它是一種方法論，計算機的數學模型就是透過遞迴來定義的一個有窮狀態自動機，他在計算機的各個領域有著廣泛的應用，如正則表示式、編譯器、資料結構等，所以要想學好計算機程式設計，就一定要學好遞迴過程。

那麼什麼是遞迴函式呢，先看一個理論上的定義：

是不是看起來有點拗口，沒關係，用通俗點的語言來說，就是有一些初始的函式是可以計算它的值得，然後由這些可計算初始值的函式透過一些運算元可以構造出更復雜的函式，不斷這樣重複下去，就會構造出越來越複雜的函式，對這些複雜函式的求值過程，就是反向呼叫，直到初始函式。

具體到C語言的情況，我們來看一個例子，比如計算1到10的和，我們定義函式F(n),用來求1到n的和，對我們的問題來說，就是求F(10)，那麼F(10)=F(9)+10，而F(9)=F(8)+9……，透過不斷的迭代展開，直到F(1)=1這個初始條件，然後開始反向計算過程，F(2)=F(1）+2=1+2=3，F(3)=F(2)+3=3+3=6…… 直到要求的函式F(10)=F(9)+10=45+10=55。

在計算機中，遞迴過程是透過一種叫做棧（先進後出）的資料結構來實現的，理論上這個過程是可以無限延伸的，但是因為計算機記憶體的有限性，遞迴的深度要受記憶體的約束，最大遞迴深度要根據記憶體使用情況來具體分析。

最後，再說一定，遞迴函式和數學歸納法有些相似，可以參考數學歸納法的過程理解遞迴過程。

正是為了好懂，才提出遞迴函式。

數學中有遞迴定義，如斐波拿茨數列，資料結構中的二叉樹等等。

部分與全體同構，如分形。

用遞迴函式實現這些具有遞迴定義的模型很方便。

如果不用遞迴，用遞推法，寫起來麻煩一些，也容易出錯。

機器語言程式碼中遞迴函式的實現也較方便，只要跳轉到入口地址就可以了，相當於goto實現迴圈。

除了C，大部分程式設計語言也支援遞迴函式，如Delphi等。

什麼是遞迴？

如果你已理解，不必再回答了。

如果你不理解，那麼，要搞懂這個問題，

我們必須首先搞懂：什麼是遞迴？

程式設計，如果到了高階程度，編寫基礎軟體，比如編譯器、圖形影象處理、訊號處理、搜尋引擎、人工智慧等，確實需要對數學非常精通。日常設計算法，如果對數學很瞭解，也是如虎添翼。但是，遞迴本身只是一種程式設計方式，根本不涉及什麼數學的東西。遞迴非常簡單，就是一個函式（或者面向物件程式設計中的類的方法）在其函式體內呼叫它自身而已。因此，這種呼叫會一直持續下去，直到到達你在程式碼中設定的條件或者記憶體溢位。

你之所以覺得困難，是因為：

1，你缺乏計算機科學的基礎知識，尤其是計算機架構、CPU指令集（組合語言）和作業系統的基礎知識。

2，你剛開始入門，還沒有鍛煉出來很好的抽象思維能力。程式設計是一種高度考驗腦力的活動，其中既有發散思維，也有羅輯思維和抽象思維。其中抽象思維非常重要，它使得你可以把握整個軟體的架構，並且使得軟體的修改、更新、升級儘可能容易。

你理解不了遞迴，首先是不懂在機器程式碼層級上（記憶體佈局和CPU指令）函式的呼叫與軟體的執行是怎麼回事；其次，是因為你還缺乏抽象思維能力。

你需要的是建立信心，從基礎學起（當然這並不意味著你需要停止你現在進行的程式設計工作），並鍛鍊自己的思維能力。

我也這麼覺得哈哈，我當初學習 C 語言時，覺得最難的就是“遞迴”了，比指標還難理解（C 語言中的指標，很多人都認為難以理解）。

那什麼是“遞迴”呢？

我有一天翻詞典時，看到詞典這麼解釋一個詞：

驚人的：用來形容驚人的形容詞。

這要麼是惡搞，要麼就是玩笑。然而在數學上確實有很多概念是用自己定義的，舉個例子：n 的階乘等於 n 乘以 n-1 的階乘，並且 0 的階乘等於 1。咋一看，似乎它並沒有說清楚什麼是階乘，但是這樣的描述，卻足以讓人知道怎樣計算階乘。例如計算 4 的階乘：

4! = 4 x 3! = 4 x 3 x 2! = 4 x 3 x 2 x 1! = 4 x 3 x 2 x 1 x 0! = 4 x 3 x 2 x 1 x 1 = 24

並不用細究階乘到底是什麼，只需要按照定義去計算即可，當然，這種定義方式必須要有一個“基礎條件”，比如階乘的“基礎條件”就是 0! = 1。如果沒有“基礎條件”，階乘只會無限往下推，沒有盡頭。

C 語言中，什麼是遞迴函式？

說了半天階乘，就是為“遞迴”做鋪墊的，如果一個概念需要用到自身，我們就稱它的定義是遞迴的。那顯然，遞迴函式一定是呼叫了自身的函式，這麼說有點虛，來看看例項吧，下面用 C 語言計算 n 的階乘。我們已經知道，遞迴最重要的就是“基礎條件”了，我們先把階乘的基礎條件寫好：

上面的程式碼實現了 0 的階乘等於 1，那如果 n 大於 0 呢？按照階乘的定義，應該是 n x fatorial(n-1)，用程式碼實現就是：

這就用 C 語言實現了計算 n 的階乘。factorial 函式呼叫了自己，所以 factorial 是遞迴函式。事實上，不僅僅是直接呼叫自己，間接呼叫自己也屬於遞迴函式。比如，A 呼叫了函式 B，函式 B 又呼叫了 A，那 A 也是遞迴函式。

那，遞迴函式是怎麼執行的呢？

為了方便解釋，我們在 factorial 函式的else 部分加幾個區域性變數：

這裡以 factorial(3) 為例，用實線箭頭表示呼叫，用虛線箭頭表示返回，右邊的框表示在呼叫和返回過程中各函式呼叫的區域性變數的變化情況。

我們看圖右邊表示儲存空間的框的變化過程，隨著函式呼叫的層層深入，儲存空間的一端逐漸增長，然後隨著函式的層層退出，儲存空間的這一端又逐漸縮短，這是一種具有特定性質的資料結構。

它的特性就是隻能在某一端增長或縮短，並且每次訪問引數和區域性變數時只能訪問這一末端的單元，而不能訪問內部的單元，比如當factorial(2)的儲存空間位於末端時，只能訪問它的引數和區域性變數，而不能訪問factorial(3)和main()的引數和區域性變數。

具有這種性質的資料結構稱為堆疊或棧（Stack）。每個函式呼叫的引數和區域性變數的儲存空間（圖裡的一個小方框）稱為一個棧幀（Stack Frame）。系統為每個程式的執行預留了棧空間，函式呼叫時就在這個棧空間裡分配棧幀，函式返回時就釋放棧幀。

可以看出，寫 C 語言遞迴函式最重要的就是一定要定義好“基礎條件”，不然函式就會永遠呼叫下去，知道系統資源耗盡程式崩潰為止。遞迴和迴圈是等價的，用迴圈能做的事用遞迴都能做，反之亦然，事實上有的程式語言（如某些LISP）只有遞迴而沒有迴圈。

計算機硬體能做的所有事情就是資料存取、運算、測試和分支、迴圈（或遞迴），在計算機上執行的高階語言寫的程式當然也不可能做到更多的事情，雖然高階語言有豐富的語法特性，但也只是為做這些事情提供一些方便。那麼，為什麼計算機是這樣設計的？為什麼想到計算機需要具有這幾種功能，而不是更多或者更少？這些要歸功於早期的計算機科學家，例如Alan Turing，他們在計算機還沒有誕生的年代從數學理論上為計算機的設計指明瞭方向。

所有的語言都可以使用遞迴，遞迴和迴圈是等價的，只不過實現方式不同而已。

一個等價的例子

求1到10累加:

迴圈 用For迴圈在迴圈體內做累加計算，終止條件是 控制變數>10遞迴 累加計算和增1計算做遞迴公式，遞迴條件 控制變數<=10遞迴的優缺點

遞迴的程式碼簡潔複雜度低 遞迴在處理複雜巢狀時，具備了迴圈無法比擬的優勢。

遞迴的記憶體使用效率略高 遞迴使用棧的空間，隨著迴圈的進行，前面遞迴函式不能結束後面的遞迴函式不斷增加，棧空間增加，但到後期，遞迴函式開始完結，棧空間會迅速釋放。相比之下，迴圈體主要使用堆空間，迴圈過程中堆空間不斷增加，迴圈結束後不會立即釋放堆空間。遞迴容易引起棧記憶體的溢位 由於遞迴函式是動態申請棧空間，透過編譯和靜態程式碼解析，無法發現記憶體的溢位的問題。因此，遞迴對程式設計師的技術能力要求較高。理論上遞迴的執行速度略快 這是由於棧的讀寫速度要高於堆。

你覺得難懂，是正常的。

遞迴函式屬於資料結構與演算法中的知識範疇，這部分內容不僅是軟體人員的基礎，同時又是難點，它需要軟體學習人員具有一定的數學水平，而且是高等數學水平，而且這部分知識中的程式碼思想都非常精簡，所以難看懂就很正常了。

最好的辦法是，不要僅僅只看書本的內容，還要經常動手編碼練一練，這樣能加快理解，並且不會遺忘。

遞迴函式初看很簡單，就是一個函式，只不過這個函式稍微特殊了一點，除了一開始需要外來引數（或者預設值），過程中的資料，又作為自身的引數，繼續執行下去了，直到滿足退出條件，才停止執行。整個函式就形成了一個迴圈。

理解這個函式是一回事，吃透它又是另一回事。平常很少用它，偶爾也能夠用得起來，不過總感覺沒有能夠把它融匯貫通，所以看到這個問題，我就進來了。

用遞迴函式可以用較簡潔的程式碼，來做一些比較規律的，用通常方法又較為麻煩的事。