C語言中的遞歸函數(shù)？

謝邀。

我也這么覺得哈哈，我當(dāng)初學(xué)習(xí) C 語言時，覺得最難的就是“遞歸”了，比指針還難理解（C 語言中的指針，很多人都認(rèn)為難以理解）。

那什么是“遞歸”呢？

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

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

這要么是惡搞，要么就是玩笑。然而在數(shù)學(xué)上確實有很多概念是用自己定義的，舉個例子：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

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

C 語言中，什么是遞歸函數(shù)？

說了半天階乘，就是為“遞歸”做鋪墊的，如果一個概念需要用到自身，我們就稱它的定義是遞歸的。那顯然，遞歸函數(shù)一定是調(diào)用了自身的函數(shù)，這么說有點虛，來看看實例吧，下面用 C 語言計算 n 的階乘。我們已經(jīng)知道，遞歸最重要的就是“基礎(chǔ)條件”了，我們先把階乘的基礎(chǔ)條件寫好：

上面的代碼實現(xiàn)了 0 的階乘等于 1，那如果 n 大于 0 呢？按照階乘的定義，應(yīng)該是 n x fatorial(n-1)，用代碼實現(xiàn)就是：

這就用 C 語言實現(xiàn)了計算 n 的階乘。factorial 函數(shù)調(diào)用了自己，所以 factorial 是遞歸函數(shù)。事實上，不僅僅是直接調(diào)用自己，間接調(diào)用自己也屬于遞歸函數(shù)。比如，A 調(diào)用了函數(shù) B，函數(shù) B 又調(diào)用了 A，那 A 也是遞歸函數(shù)。

那，遞歸函數(shù)是怎么執(zhí)行的呢？

為了方便解釋，我們在 factorial 函數(shù)的else 部分加幾個局部變量：

這里以 factorial(3) 為例，用實線箭頭表示調(diào)用，用虛線箭頭表示返回，右邊的框表示在調(diào)用和返回過程中各函數(shù)調(diào)用的局部變量的變化情況。

我們看圖右邊表示存儲空間的框的變化過程，隨著函數(shù)調(diào)用的層層深入，存儲空間的一端逐漸增長，然后隨著函數(shù)的層層退出，存儲空間的這一端又逐漸縮短，這是一種具有特定性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。

它的特性就是只能在某一端增長或縮短，并且每次訪問參數(shù)和局部變量時只能訪問這一末端的單元，而不能訪問內(nèi)部的單元，比如當(dāng)factorial(2)的存儲空間位于末端時，只能訪問它的參數(shù)和局部變量，而不能訪問factorial(3)和main()的參數(shù)和局部變量。

具有這種性質(zhì)的數(shù)據(jù)結(jié)構(gòu)稱為堆棧或棧（Stack）。每個函數(shù)調(diào)用的參數(shù)和局部變量的存儲空間（圖里的一個小方框）稱為一個棧幀（Stack Frame）。系統(tǒng)為每個程序的運行預(yù)留了棧空間，函數(shù)調(diào)用時就在這個棧空間里分配棧幀，函數(shù)返回時就釋放棧幀。

可以看出，寫 C 語言遞歸函數(shù)最重要的就是一定要定義好“基礎(chǔ)條件”，不然函數(shù)就會永遠(yuǎn)調(diào)用下去，知道系統(tǒng)資源耗盡程序崩潰為止。遞歸和循環(huán)是等價的，用循環(huán)能做的事用遞歸都能做，反之亦然，事實上有的編程語言（如某些LISP）只有遞歸而沒有循環(huán)。

計算機硬件能做的所有事情就是數(shù)據(jù)存取、運算、測試和分支、循環(huán)（或遞歸），在計算機上運行的高級語言寫的程序當(dāng)然也不可能做到更多的事情，雖然高級語言有豐富的語法特性，但也只是為做這些事情提供一些方便。那么，為什么計算機是這樣設(shè)計的？為什么想到計算機需要具有這幾種功能，而不是更多或者更少？這些要歸功于早期的計算機科學(xué)家，例如Alan Turing，他們在計算機還沒有誕生的年代從數(shù)學(xué)理論上為計算機的設(shè)計指明了方向。

歡迎在評論區(qū)一起討論，質(zhì)疑。文章都是手打原創(chuàng)，每天最淺顯的介紹C語言、linux等嵌入式開發(fā)，喜歡我的文章就關(guān)注一波吧，可以看到最新更新和之前的文章哦。