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

[[315767]]

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

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

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

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

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

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

將這兩句話轉(zhuǎn)換為數(shù)學(xué)語言，也就是：

factorial()函數(shù)的數(shù)學(xué)描述

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

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

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

再來看一個例子

為了加深對遞歸的理解，這里再舉一個例子，請看下面這段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() 函數(shù)的C語言代碼

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

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

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

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

此時應(yīng)注意，test_0~3() 都是在執(zhí)行到“test(left, mid)”時發(fā)生遞歸調(diào)用的，因此它們將返回到“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”，調(diào)用 test_5(3, 4)
• test_5(3, 4)：輸出“before：3 3 4”，調(diào)用 test_6(3, 3)
• test_6(3, 3)：因為 3>=3，所以直接返回 test_5(3, 4)

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

函數(shù)返回到 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 

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

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

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

0 0 10 1 23 3 43 4 50 2 5 

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

二分數(shù)組過程

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

小結(jié)

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