初學者在學習C語言的過程中，遇到“遞歸”的概念時，常常會感到迷惑。坦誠地說，“遞歸”在編程語言中的確是一個比較難理解的概念，而且“遞歸”能解決的問題，一般循環語句也能解決，從某種程度上來說，C語言中的“遞歸”和循環語句是等價的，既然如此，為什么C語言不“丟棄”難以理解的“遞歸”呢?

[[315767]]

C語言為什么不丟棄“遞歸”?

其實，“遞歸”究竟是否難以理解取決于程序員看問題的角度。應該明白，C語言程序是為人們現實生活需求服務的，在我看來，如果脫離了實際問題，僅從編程語言的角度來看問題，“遞歸”的確比較難理解，相反，如果結合要實際解決的問題，有時“遞歸”反而更加清晰易懂。請看下面這段C語言代碼示例：

int factorial(int n){    if(0 == n)        return 1;    else        return n*factorial(n-1);} 

factorial() 函數是一個典型的遞歸函數，雖然它的代碼很簡單，但如果僅從編程語言的角度來理解這個函數，的確有些難度——當 n!=0 時，函數似乎永遠在嵌套自己，雖說粗暴的逐步分析能夠得到函數的輸出，但是稍不留神就會出錯。

現在換個角度考慮 factorial() 函數，嘗試從該函數要解決的“實際需求”上分析，應該不難得到 factorial() 函數其實在說：

• 如果 n 等于 0，那么 f(n) 等于 1，也即 f(0) 等于 1
• 如果 n 不等于 0，那么 f(n) 等于 n*f(n-1)

將這兩句話轉換為數學語言，也就是：

factorial()函數的數學描述

如果限定 n 為不小于 0 的整數，那么這顯然就是數學中整數階乘的定義，也即 factorial(n) 函數的輸出為 n!。可以看出，遞歸函數 factorial() 其實就是直白的使用C語言“描述”了 n! 的數學定義，因此從這個角度來看，“遞歸”似乎又不是那么難理解。

當然了，使用C語言的循環語句編寫程序計算 n! 也是可以的，讀者可自行編寫，應該能夠發現，循環語句計算 n! 更像是使用“笨方法”一點點的計算，它與“遞歸”實現從設計思維上來看是不同的。

因此，從上面這個例子可以看出，C語言中的“遞歸”倒不像是一種語法，而是一種“編程思維”，所以“丟棄”便無從說起了。當然了，嚴格來說，C語言對“遞歸”也是做了一定的支持，至少遞歸函數就屬于C語言的一種語法，這其實與C語言的基本設計思想有關：C語言從誕生至今，有一個特點是始終堅持的——盡可能的保持簡潔，給程序員比較大的自由。所以，既然“遞歸”思維是一個不錯的思維，C語言當然要提供遞歸函數予以支持了。

再來看一個例子

為了加深對遞歸的理解，這里再舉一個例子，請看下面這段C語言代碼：

#include void test(int left, int right) { if (left >= right) return; int mid = (left+right) /2; printf("before: %d %d %d\n", left, mid, right); test(left, mid); test(mid+1, right); printf("after : %d %d %d\n", left, mid, right);} int main() { test(0, 5); return 0;} 

test() 函數的C語言代碼

test() 函數顯然是一個遞歸函數，它的代碼也比較簡單，只不過在其內部遞歸調用了兩次，稍稍復雜了一些。接下來，我們將分別從編程語言角度，和實際需求角度分別分析 test() 函數的功能。

首先，從編程語言角度來看，顯然 test() 函數會被多次調用，為了便于討論，每發生一次 test() 函數調用，我們就在函數名后加一個后綴“_xx”。

test() 函數首次被調用是在 main() 函數中，進入 test() 函數后，程序會先遞歸調用 test(left, mid); 行此時可寫作：

• test_0(0, 5)：輸出“before：0 2 5”，調用 test_1(0, 2)
• test_1(0, 2)：輸出“before：0 1 2”，調用 test_2(0, 1)
• test_2(0, 1)：輸出“before：0 0 1”，調用 test_3(0, 0)
• test_3(0, 0)：因為 0>=0，所以直接返回 test_2(0, 1)

此時應注意，test_0~3() 都是在執行到“test(left, mid)”時發生遞歸調用的，因此它們將返回到“test(mid+1, right)”處。

返回到 test_2(0, 1) 時，left=0, right=1, mid=0，因此 test(mid+1, right) 會直接返回，輸出“after：0 0 1”;接著返回 test_1(0, 2)，同理，輸出“after：0 1 2”;接著返回 test_0(0, 5) 的 test(mid+1, right); 行，此時 left=0, right=5, mid=2，接下來的過程將如下進行：

• test_4(3, 5)：輸出“before：3 4 5”，調用 test_5(3, 4)
• test_5(3, 4)：輸出“before：3 3 4”，調用 test_6(3, 3)
• test_6(3, 3)：因為 3>=3，所以直接返回 test_5(3, 4)

此時應注意 test4~6() 是在執行 “test(mid+1, right)”時發生遞歸調用的，因此它們將返回到“printf("after:...”處。

函數返回到 test_5(3, 4) 后，此時 left=3, right=4, mid=3，因此 輸出“after：3 3 4”，并返回 test_4(3, 5)，輸出“after：3 4 5”，并返回 test_0(0, 5)，輸出“after：0 2 5”。整理一下，得到上述C語言程序的輸出如下：

before: 0 2 5before: 0 1 2before: 0 0 1after : 0 0 1after : 0 1 2before: 3 4 5before: 3 3 4after : 3 3 4after : 3 4 5after : 0 2 5 

可見，從編程語言角度來分析遞歸函數，的確是一件比較吃力的事情，若是輸入給 test(0, 105) 函數的參數更寬一些，基本上可以認為是不可分析的。現在我們嘗試從實際需求角度理解遞歸函數 test() 的功能，應該能夠輕易得到以下信息：

• 當輸入的 left 不小于 right 時，函數直接返回
• 否則 test() 函數將打印 left 與 right 以及它倆的平均整數值 mid
• 接著，令 right=mid，并重復上述過程;令 left=mid+1，并重復上述過程
• 打印在這之后的 left，mid，right

稍加理解，基本應該能明白 test() 函數的功能了：mid 是 left 和 right 的二分中間值，因此 test(left, mid) 可以看作是二分之后的左半部分，test(mid+1, right) 則可以看作是二分之后的右半部分，因此 test() 函數的作用其實就是在不停的二分 left~right 區間，一直到不能繼續二分為止(left>=right)，這一過程是逐步遞歸的，因此 test() 函數也會逐步輸出二分的結果。以分析“after：...”輸出為例，test(0, 5) 會依次輸出：

0 0 10 1 23 3 43 4 50 2 5 

這與從編程語言角度分析的結果是一致的。理解這一點后，現在我們引入應用實例，假定有一個數組 {3,2,5,1,4}，調用 test(0,5) 逐步二分該數組，過程應該如下圖所示：

二分數組過程

至此，我們便從實際需求角度分析了遞歸函數，可見，理解遞歸函數其實就是理解其設計，站在更高處從大局出發理解其含義的。

小結

“遞歸”不能算是C語言中的語法，它更像是一種思想，因此“C語言為什么不丟棄“遞歸””這種說法是沒有意義的。本文還通過兩個實例，從編程語言和實際應用兩個角度討論了如何分析C語言中的遞歸函數，可見，遞歸有時的確能夠簡潔的解決問題。不過不得不承認，遞歸的確是一個較難理解的概念，而且遞歸函數也比較難以調試，消耗棧空間巨大，因此在實際的C語言程序開發中，除非遞歸能夠帶來極大的便利，否則不建議使用遞歸，而是盡量嘗試使用循環解決問題。