第?5?章?深入理解函數 · Linux C 一站式學習

# 第?5?章?深入理解函數 **目錄** + [1\. return語句](ch05s01.html) + [2\. 增量式開發](ch05s02.html) + [3\. 遞歸](ch05s03.html) ## 1.?return語句之前我們一直在`main`函數中使用`return`語句，現在是時候全面深入地學習一下了。在有返回值的函數中，`return`語句的作用是提供整個函數的返回值，并結束當前函數返回到調用它的地方。在沒有返回值的函數中也可以使用`return`語句，例如當檢查到一個錯誤時提前結束當前函數的執行并返回： ``` #include <math.h> void print_logarithm(double x) { if (x <= 0.0) { printf("Positive numbers only, please.\n"); return; } printf("The log of x is %f", log(x)); } ``` 這個函數首先檢查參數`x`是否大于0，如果`x`不大于0就打印錯誤提示，然后提前結束函數的執行返回到調用者，只有當`x`大于0時才能求對數，在打印了對數結果之后到達函數體的末尾，自然地結束執行并返回。注意，使用數學函數`log`需要包含頭文件`math.h`，由于`x`是浮點數，應該與同類型的數做比較，所以寫成0.0。在[第?2?節 “if/else語句”](ch04s02.html#cond.ifelse)中我們定義了一個檢查奇偶性的函數，如果是奇數就打印`x is odd.`，如果是偶數就打印`x is even.`。事實上這個函數并不十分好用，我們定義一個檢查奇偶性的函數往往不是為了打印兩個字符串就完了，而是為了根據奇偶性的不同分別執行不同的后續動作。我們可以把它改成一個返回布爾值的函數： ``` int is_even(int x) { if (x % 2 == 0) return 1; else return 0; } ``` 有些人喜歡寫成`return(1);`這種形式也可以，表達式外面套括號表示改變運算符優先級，在這里不起任何作用。我們可以這樣調用這個函數： ``` int i = 19; if (is_even(i)) { /* do something */ } else { /* do some other thing */ } ``` 返回布爾值的函數是一類非常有用的函數，在程序中通常充當控制表達式，函數名通常帶有`is`或`if`等表示判斷的詞，這類函數也叫做謂詞（Predicate）。`is_even`這個函數寫得有點啰嗦，`x % 2`這個表達式本來就有0值或非0值，直接把這個值當作布爾值返回就可以了： ``` int is_even(int x) { return !(x % 2); } ``` 函數的返回值應該這樣理解：_函數返回一個值相當于定義一個和返回值類型相同的臨時變量并用`return`后面的表達式來初始化_。例如上面的函數調用相當于這樣的過程： ``` int 臨時變量 = !(x % 2); 函數退出，局部變量x的存儲空間釋放; if (臨時變量) { /* 臨時變量用完就釋放 */ /* do something */ } else { /* do some other thing */ } ``` 當`if`語句對函數的返回值做判斷時，函數已經退出，局部變量`x`已經釋放，所以不可能在這時候才計算表達式`!(x % 2)`的值，表達式的值必然是事先計算好了存在一個臨時變量里的，然后函數退出，局部變量釋放，`if`語句對這個臨時變量的值做判斷。注意，雖然函數的返回值可以看作是一個臨時變量，但我們只是讀一下它的值，讀完值就釋放它，而不能往它里面存新的值，換句話說，_函數的返回值不是左值，或者說函數調用表達式不能做左值_，因此下面的賦值語句是非法的： ``` is_even(20) = 1; ``` 在[第?3?節 “形參和實參”](ch03s03.html#func.paraarg)中講過，C語言的傳參規則是Call by Value，按值傳遞，現在我們知道返回值也是按值傳遞的，即便返回語句寫成`return x;`，返回的也是變量`x`的值，而非變量`x`本身，因為變量`x`馬上就要被釋放了。在寫帶有`return`語句的函數時要小心檢查所有的代碼路徑（Code Path）。有些代碼路徑在任何條件下都執行不到，這稱為Dead Code，例如把&&和||運算符記混了（據我了解初學者犯這個低級錯誤的不在少數），寫出如下代碼： ``` void foo(int x, int y) { if (x >= 0 || y >= 0) { printf("both x and y are positive.\n"); return; } else if (x < 0 || y < 0) { printf("both x and y are negetive.\n"); return; } printf("x has a different sign from y.\n"); } ``` 最后一行`printf`永遠都沒機會被執行到，是一行Dead Code。有Dead Code就一定有Bug，你寫的每一行代碼都是想讓程序在某種情況下去執行的，你不可能故意寫出一行永遠不會被執行的代碼，如果程序在任何情況下都不會去執行它，說明跟你預想的不一樣，要么是你對所有可能的情況分析得不正確，也就是邏輯錯誤，要么就是像上例這樣的筆誤，語義錯誤。還有一些時候，對程序中所有可能的情況分析得不夠全面將導致漏掉一些代碼路徑，例如： ``` int absolute_value(int x) { if (x < 0) { return -x; } else if (x > 0) { return x; } } ``` 這個函數被定義為返回`int`，就應該在任何情況下都返回`int`，但是上面這個程序在`x==0`時安靜地退出函數，什么也不返回，C語言對于這種情況會返回什么結果是未定義的，通常返回不確定的值，等學到[第?1?節 “函數調用”](ch19s01.html#asmc.funccall)你就知道為什么了。另外注意這個例子中把-號當負號用而不是當減號用，事實上+號也可以這么用。正負號是單目運算符，而加減號是雙目運算符，正負號的優先級和邏輯非運算符相同，比加減的優先級要高。以上兩段代碼都不會產生編譯錯誤，編譯器只做語法檢查和最簡單的語義檢查，而不檢查程序的邏輯[[7](#ftn.id2721968)]。雖然到現在為止你見到了各種各樣的編譯器錯誤提示，也許你已經十分討厭編譯器報錯了，但很快你就會認識到，如果程序中有錯誤編譯器還不報錯，那一定比報錯更糟糕。比如上面的絕對值函數，在你測試的時候運行得很好，也許是你沒有測到`x==0`的情況，也許剛好在你的環境中`x==0`時返回的不確定值就是0，然后你放心地把它集成到一個數萬行的程序之中。然后你把這個程序交給用戶，起初的幾天里相安無事，之后每過幾個星期就有用戶報告說程序出錯，但每次出錯的現象都不一樣，而且這個錯誤很難復現，你想讓它出現時它就不出現，在你毫無防備時它又突然冒出來了。然后你花了大量的時間在數萬行的程序中排查哪里錯了，幾天之后終于幸運地找到了這個函數的Bug，這時候你就會想，如果當初編譯器能報個錯多好啊！所以，如果編譯器報錯了，不要責怪編譯器太過于挑剔，它幫你節省了大量的調試時間。另外，在`math.h`中有一個`fabs`函數就是求絕對值的，我們通常不必自己寫絕對值函數。 ### 習題 1、編寫一個布爾函數`int is_leap_year(int year)`，判斷參數`year`是不是閏年。如果某年份能被4整除，但不能被100整除，那么這一年就是閏年，此外，能被400整除的年份也是閏年。 2、編寫一個函數`double myround(double x)`，輸入一個小數，將它四舍五入。例如`myround(-3.51)`的值是-4.0，`myround(4.49)`的值是4.0。可以調用`math.h`中的庫函數`ceil`和`floor`實現這個函數。 * * * [[7](#id2721968)] 有的代碼路徑沒有返回值的問題編譯器是可以檢查出來的，如果編譯時加`-Wall`選項會報警告。 ## 2.?增量式開發目前為止你看到了很多示例代碼，也在它們的基礎上做了很多改動并在這個過程中鞏固所學的知識。但是如果從頭開始編寫一個程序解決某個問題，應該按什么步驟來寫呢？本節提出一種增量式（Incremental）開發的思路，很適合初學者。現在問題來了：我們要編一個程序求圓的面積，圓的半徑以兩個端點的座標(x1, y1)和(x2, y2)給出。首先分析和分解問題，把大問題分解成小問題，再對小問題分別求解。這個問題可分為兩步： 1. 由兩個端點座標求半徑的長度，我們知道平面上兩點間距離的公式是： distance?=?√((x2-x1)2+(y2-y1)2) 括號里的部分都可以用我們學過的C語言表達式來表示，求平方根可以用`math.h`中的`sqrt`函數，因此這個小問題全部都可以用我們學過的知識解決。這個公式可以實現成一個函數，參數是兩點的座標，返回值是`distance`。 2. 上一步算出的距離是圓的半徑，已知圓的半徑之后求面積的公式是： area?=?π·radius2 也可以用我們學過的C語言表達式來解決，這個公式也可以實現成一個函數，參數是`radius`，返回值是`area`。首先編寫`distance`這個函數，我們已經明確了它的參數是兩點的座標，返回值是兩點間距離，可以先寫一個簡單的函數定義： ``` double distance(double x1, double y1, double x2, double y2) { return 0.0; } ``` 初學者寫到這里就已經不太自信了：這個函數定義寫得對嗎？雖然我是按我理解的語法規則寫的，但書上沒有和這個一模一樣的例子，萬一不小心遺漏了什么呢？既然不自信就不要再往下寫了，沒有一個平穩的心態來寫程序很可能會引入Bug。所以在函數定義中插一個`return 0.0`立刻結束掉它，然后立刻測試這個函數定義得有沒有錯： ``` int main(void) { printf("distance is %f\n", distance(1.0, 2.0, 4.0, 6.0)); return 0; } ``` 編譯，運行，一切正常。這時你就會建立起信心了：既然沒問題，就不用管它了，繼續往下寫。在測試時給這個函數的參數是(1.0, 2.0)和(4.0, 6.0)，兩點的`x`座標距離是3.0，`y`座標距離是4.0，因此兩點間距離應該是5.0，你必須事先知道正確答案是5.0，這樣你才能測試程序計算的結果對不對。當然，現在函數還沒實現，計算結果肯定是不對的。現在我們再往函數里添一點代碼： ``` double distance(double x1, double y1, double x2, double y2) { double dx = x2 - x1; double dy = y2 - y1; printf("dx is %f\ndy is %f\n", dx, dy); return 0.0; } ``` 如果你不確定`dx`和`dy`這樣初始化行不行，那么就此打住，在函數里插一條打印語句把`dx`和`dy`的值打出來看看。把它和上面的`main`函數一起編譯運行，由于我們事先知道結果應該是3.0和4.0，因此能夠驗證程序算得對不對。一旦驗證無誤，函數里的這句打印就可以撤掉了，像這種打印語句，以及我們用來測試的`main`函數，都起到了類似腳手架（Scaffold）的作用：在蓋房子時很有用，但它不是房子的一部分，房子蓋好之后就可以拆掉了。房子蓋好之后可能還需要維修、加蓋、翻新，又要再加上腳手架，這很麻煩，要是當初不用拆就好了，可是不拆不行，不拆多難看啊。寫代碼卻可以有一個更高明的解決辦法：把Scaffolding的代碼注釋掉。 ``` double distance(double x1, double y1, double x2, double y2) { double dx = x2 - x1; double dy = y2 - y1; /* printf("dx is %f\ndy is %f\n", dx, dy); */ return 0.0; } ``` 這樣如果以后出了新的Bug又需要跟蹤調試時，還可以把這句重新加進代碼中使用。兩點的x座標距離和y座標距離都沒問題了，下面求它們的平方和： ``` double distance(double x1, double y1, double x2, double y2) { double dx = x2 - x1; double dy = y2 - y1; double dsquared = dx * dx + dy * dy; printf("dsquared is %f\n", dsquared); return 0.0; } ``` 然后再編譯、運行，看看是不是得25.0。這樣的增量式開發非常適合初學者，每寫一行代碼都編譯運行，確保沒問題了再寫一下行，一方面在寫代碼時更有信心，另一方面也方便了調試：總是有一個先前的正確版本做參照，改動之后如果出了問題，幾乎可以肯定就是剛才改的那行代碼出的問題，這樣就避免了必須從很多行代碼中查找分析到底是哪一行出的問題。在這個過程中`printf`功不可沒，你懷疑哪一行代碼有問題，就插一個`printf`進去看看中間的計算結果，任何錯誤都可以通過這個辦法找出來。以后我們會介紹程序調試工具`gdb`，它提供了更強大的調試功能幫你分析更隱蔽的錯誤。但即使有了`gdb`，`printf`這個最原始的辦法仍然是最直接、最有效的。最后一步，我們完成這個函數： **例?5.1.?distance函數** ``` #include <math.h> #include <stdio.h> double distance(double x1, double y1, double x2, double y2) { double dx = x2 - x1; double dy = y2 - y1; double dsquared = dx * dx + dy * dy; double result = sqrt(dsquared); return result; } int main(void) { printf("distance is %f\n", distance(1.0, 2.0, 4.0, 6.0)); return 0; } ``` 然后編譯運行，看看是不是得5.0。隨著編程經驗越來越豐富，你可能每次寫若干行代碼再一起測試，而不是像現在這樣每寫一行就測試一次，但不管怎么樣，增量式開發的思路是很有用的，它可以幫你節省大量的調試時間，不管你有多強，都不應該一口氣寫完整個程序再編譯運行，那幾乎是一定會有Bug的，到那時候再找Bug就難了。這個程序中引入了很多臨時變量：`dx`、`dy`、`dsquared`、`result`，如果你有信心把整個表達式一次性寫好，也可以不用臨時變量： ``` double distance(double x1, double y1, double x2, double y2) { return sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1)); } ``` 這樣寫簡潔得多了。但如果寫錯了呢？只知道是這一長串表達式有錯，根本不知道錯在哪，而且整個函數就一個語句，插`printf`都沒地方插。所以用臨時變量有它的好處，使程序更清晰，調試更方便，而且有時候可以避免不必要的計算，例如上面這一行表達式要把`(x2-x1)`計算兩遍，如果算完`(x2-x1)`把結果存在一個臨時變量`dx`里，就不需要再算第二遍了。接下來編寫`area`這個函數： ``` double area(double radius) { return 3.1416 * radius * radius; } ``` 給出兩點的座標求距離，給出半徑求圓的面積，這兩個子問題都解決了，如何把它們組合起來解決整個問題呢？給出半徑的兩端點座標(1.0, 2.0)和(4.0, 6.0)求圓的面積，先用`distance`函數求出半徑的長度，再把這個長度傳給`area`函數： ``` double radius = distance(1.0, 2.0, 4.0, 6.0); double result = area(radius); ``` 也可以這樣： ``` double result = area(distance(1.0, 2.0, 4.0, 6.0)); ``` 我們一直把“給出半徑的兩端點座標求圓的面積”這個問題當作整個問題來看，如果它也是一個更大的程序當中的子問題呢？我們可以把先前的兩個函數組合起來做成一個新的函數以便日后使用： ``` double area_point(double x1, double y1, double x2, double y2) { return area(distance(x1, y1, x2, y2)); } ``` 還有另一種組合的思路，不是把`distance`和`area`兩個函數調用組合起來，而是把那兩個函數中的語句組合到一起： ``` double area_point(double x1, double y1, double x2, double y2) { double dx = x2 - x1; double dy = y2 - y1; double radius = sqrt(dx * dx + dy * dy); return 3.1416 * radius * radius; } ``` 這樣組合是不理想的。這樣組合了之后，原來寫的`distance`和`area`兩個函數還要不要了呢？如果不要了刪掉，那么如果有些情況只需要求兩點間的距離，或者只需要給定半徑長度求圓的面積呢？`area_point`把所有語句都寫在一起，太不靈活了，滿足不了這樣的需要。如果保留`distance`和`area`同時也保留這個`area_point`怎么樣呢？`area_point`和`distance`有相同的代碼，一旦在`distance`函數中發現了Bug，或者要升級`distance`這個函數采用更高的計算精度，那么不僅要修改`distance`，還要記著修改`area_point`，同理，要修改`area`也要記著修改`area_point`，維護重復的代碼是非常容易出錯的，在任何時候都要盡量避免。因此，_盡可能復用（Reuse）以前寫的代碼，避免寫重復的代碼_。封裝就是為了復用，把解決各種小問題的代碼封裝成函數，在解決第一個大問題時可以用這些函數，在解決第二個大問題時可以復用這些函數。解決問題的過程是把大的問題分成小的問題，小的問題再分成更小的問題，這個過程在代碼中的體現就是函數的分層設計（Stratify）。`distance`和`area`是兩個底層函數，解決一些很小的問題，而`area_point`是一個上層函數，上層函數通過調用底層函數來解決更大的問題，底層和上層函數都可以被更上一層的函數調用，最終所有的函數都直接或間接地被`main`函數調用。如下圖所示： **圖?5.1.?函數的分層設計** ![函數的分層設計](https://box.kancloud.cn/2016-04-02_56ff80d0c9a3b.png) ## 3.?遞歸如果定義一個概念需要用到這個概念本身，我們稱它的定義是遞歸的（Recursive）。例如： frabjuous an adjective used to describe something that is frabjuous. 這只是一個玩笑，如果你在字典上看到這么一個詞條肯定要怒了。然而數學上確實有很多概念是用它自己來定義的，比如n的階乘（Factorial）是這樣定義的：n的階乘等于n乘以n-1的階乘。如果這樣就算定義完了，恐怕跟上面那個詞條有異曲同工之妙了：n-1的階乘是什么？是n-1乘以n-2的階乘。那n-2的階乘又是什么？這樣下去永遠也沒完。因此需要定義一個最關鍵的基礎條件（Base Case）：0的階乘等于1。 0!?=?1 n!?=?n?·?(n-1)! 因此，3!=3*2!，2!=2*1!，1!=1*0!=1*1=1，正因為有了Base Case，才不會永遠沒完地數下去，知道了1!=1我們再反過來算回去，2!=2*1!=2*1=2，3!=3*2!=3*2=6。下面用程序來完成這一計算過程，我們要寫一個計算階乘的函數`factorial`，先把Base Case這種最簡單的情況寫進去： ``` int factorial(int n) { if (n == 0) return 1; } ``` 如果參數`n`不是0應該`return`什么呢？根據定義，應該`return n*factorial(n-1);`，為了下面的分析方便，我們引入幾個臨時變量把這個語句拆分一下： ``` int factorial(int n) { if (n == 0) return 1; else { int recurse = factorial(n-1); int result = n * recurse; return result; } } ``` `factorial`這個函數居然可以自己調用自己？是的。自己直接或間接調用自己的函數稱為遞歸函數。這里的`factorial`是直接調用自己，有些時候函數A調用函數B，函數B又調用函數A，也就是函數A間接調用自己，這也是遞歸函數。如果你覺得迷惑，可以把`factorial(n-1)`這一步看成是在調用另一個函數－－另一個有著相同函數名和相同代碼的函數，調用它就是跳到它的代碼里執行，然后再返回`factorial(n-1)`這個調用的下一步繼續執行。我們以`factorial(3)`為例分析整個調用過程，如下圖所示： **圖?5.2.?factorial(3)的調用過程** ![factorial(3)的調用過程](https://box.kancloud.cn/2016-04-02_56ff80d0dc815.png) 圖中用實線箭頭表示調用，用虛線箭頭表示返回，右側的框表示在調用和返回過程中各層函數調用的存儲空間變化情況。 1. `main()`有一個局部變量`result`，用一個框表示。 2. 調用`factorial(3)`時要分配參數和局部變量的存儲空間，于是在`main()`的下面又多了一個框表示`factorial(3)`的參數和局部變量，其中`n`已初始化為3。 3. `factorial(3)`又調用`factorial(2)`，又要分配`factorial(2)`的參數和局部變量，于是在`main()`和`factorial(3)`下面又多了一個框。[第?4?節 “全局變量、局部變量和作用域”](ch03s04.html#func.localvar)講過，每次調用函數時分配參數和局部變量的存儲空間，退出函數時釋放它們的存儲空間。`factorial(3)`和`factorial(2)`是兩次不同的調用，`factorial(3)`的參數`n`和`factorial(2)`的參數`n`各有各的存儲單元，雖然我們寫代碼時只寫了一次參數`n`，但運行時卻是兩個不同的參數`n`。并且由于調用`factorial(2)`時`factorial(3)`還沒退出，所以兩個函數調用的參數`n`同時存在，所以在原來的基礎上多畫一個框。 4. 依此類推，請讀者對照著圖自己分析整個調用過程。讀者會發現這個過程和前面我們用數學公式計算3!的過程是一樣的，都是先一步步展開然后再一步步收回去。我們看上圖右側存儲空間的變化過程，隨著函數調用的層層深入，存儲空間的一端逐漸增長，然后隨著函數調用的層層返回，存儲空間的這一端又逐漸縮短，并且每次訪問參數和局部變量時只能訪問這一端的存儲單元，而不能訪問內部的存儲單元，比如當`factorial(2)`的存儲空間位于末端時，只能訪問它的參數和局部變量，而不能訪問`factorial(3)`和`main()`的參數和局部變量。具有這種性質的數據結構稱為堆棧或棧（Stack），隨著函數調用和返回而不斷變化的這一端稱為棧頂，每個函數調用的參數和局部變量的存儲空間（上圖的每個小方框）稱為一個棧幀（Stack Frame）。操作系統為程序的運行預留了一塊棧空間，函數調用時就在這個棧空間里分配棧幀，函數返回時就釋放棧幀。在寫一個遞歸函數時，你如何證明它是正確的？像上面那樣跟蹤函數的調用和返回過程算是一種辦法，但只是`factorial(3)`就已經這么麻煩了，如果是`factorial(100)`呢？雖然我們已經證明了`factorial(3)`是正確的，因為它跟我們用數學公式計算的過程一樣，結果也一樣，但這不能代替`factorial(100)`的證明，你怎么辦？別的函數你可以跟蹤它的調用過程去證明它的正確性，因為每個函數只調用一次就返回了，但是對于遞歸函數，這么跟下去只會跟得你頭都大了。事實上并不是每個函數調用都需要鉆進去看的。我們在調用`printf`時沒有鉆進去看它是怎么打印的，我們只是_相信_它能打印，能正確完成它的工作，然后就繼續寫下面的代碼了。在上一節中，我們寫了`distance`和`area`函數，然后立刻測試證明了這兩個函數是正確的，然后我們寫`area_point`時調用了這兩個函數： ``` return area(distance(x1, y1, x2, y2)); ``` 在寫這一句的時候，我們需要鉆進`distance`和`area`函數中去走一趟才知道我們調用得是否正確嗎？不需要，因為我們已經_相信_這兩個函數能正確工作了，也就是相信把座標傳給`distance`它就能返回正確的距離，把半徑傳給`area`它就能返回正確的面積，因此調用它們去完成另外一件工作也應該是正確的。這種“相信”稱為Leap of Faith，首先相信一些結論，然后再用它們去證明另外一些結論。在寫`factorial(n)`的代碼時寫到這個地方： ``` ... int recurse = factorial(n-1); int result = n * recurse; ... ``` 這時，如果我們相信`factorial(n-1)`是正確的，也就是相信傳給它`n-1`它就能返回(n-1)!，那么`recurse`就是(n-1)!，那么`result`就是n*(n-1)!，也就是n!，這正是我們要返回的`factorial(n)`的結果。當然這有點奇怪：我們還沒寫完`factorial`這個函數，憑什么要相信`factorial(n-1)`是正確的？可Leap of Faith本身就是Leap（跳躍）的，不是嗎？_如果你相信你正在寫的遞歸函數是正確的，并調用它，然后在此基礎上寫完這個遞歸函數，那么它就會是正確的，從而值得你相信它正確。_ 這么說好像有點兒玄，我們從數學上嚴格證明一下`factorial`函數的正確性。剛才說了，`factorial(n)`的正確性依賴于`factorial(n-1)`的正確性，只要后者正確，在后者的結果上乘個`n`返回這一步顯然也沒有疑問，那么我們的函數實現就是正確的。因此要證明`factorial(n)`的正確性就是要證明`factorial(n-1)`的正確性，同理，要證明`factorial(n-1)`的正確性就是要證明`factorial(n-2)`的正確性，依此類推下去，最后是：要證明`factorial(1)`的正確性就是要證明`factorial(0)`的正確性。而`factorial(0)`的正確性不依賴于別的函數調用，它就是程序中的一個小的分支`return 1;`，這個1是我們根據階乘的定義寫的，肯定是正確的，因此`factorial(1)`的實現是正確的，因此`factorial(2)`也正確，依此類推，最后`factorial(n)`也是正確的。其實這就是在中學時學的數學歸納法（Mathematical Induction），用數學歸納法來證明只需要證明兩點：Base Case正確，遞推關系正確。_寫遞歸函數時一定要記得寫Base Case_，否則即使遞推關系正確，整個函數也不正確。如果`factorial`函數漏掉了Base Case： ``` int factorial(int n) { int recurse = factorial(n-1); int result = n * recurse; return result; } ``` 那么這個函數就會永遠調用下去，直到操作系統為程序預留的棧空間耗盡程序崩潰（段錯誤）為止，這稱為無窮遞歸（Infinite recursion）。到目前為止我們只學習了全部C語法的一個小的子集，但是現在應該告訴你：這個子集是完備的，它本身就可以作為一門編程語言了，以后還要學習很多C語言特性，但全部都可以用已經學過的這些特性來代替。也就是說，以后要學的C語言特性會使代碼寫起來更加方便，但不是必不可少的，現在學的這些已經完全覆蓋了[第?1?節 “程序和編程語言”](intro.program.html "1.?程序和編程語言")講的五種基本指令了。有的讀者會說循環還沒講到呢，是的，循環在下一章才講，但有一個重要的結論就是_遞歸和循環是等價的_，用循環能做的事用遞歸都能做，反之亦然，事實上有的編程語言（比如某些LISP實現）只有遞歸而沒有循環。計算機指令能做的所有事情就是數據存取、運算、測試和分支、循環（或遞歸），在計算機上運行高級語言寫的程序最終也要翻譯成指令，指令做不到的事情高級語言寫的程序肯定也做不到，雖然高級語言有豐富的語法特性，但也只是比指令寫起來更方便而已，能做的事情是一樣多的。那么，為什么計算機要設計成這樣？在設計時怎么想到計算機應該具備這幾樣功能，而不是更多或更少的功能？這些要歸功于早期的計算機科學家，例如Alan Turing，他們在計算機還沒有誕生的年代就從數學理論上為計算機的設計指明了方向。有興趣的讀者可以參考有關計算理論的教材，例如[[IATLC]](bi01.html#bibli.iatlc "Introduction to Automata Theory, Languages, and Computation")。遞歸絕不只是為解決一些奇技淫巧的數學題[[8](#ftn.id2723765)]而想出來的招，它是計算機的精髓所在，也是編程語言的精髓所在。我們學習在C的語法時已經看到很多遞歸定義了，例如在[第?1?節 “數學函數”](ch03s01.html#func.mathfunc)講過的語法規則中，“表達式”就是遞歸定義的： _表達式_?→?_表達式_(參數列表) 參數列表?→?_表達式_,?_表達式_,?... 再比如在[第?1?節 “if語句”](ch04s01.html#cond.if)講過的語規則中，“語句”也是遞歸定義的： _語句_?→?if?(控制表達式)?_語句_ 可見編譯器在解析我們寫的程序時一定也用了大量的遞歸，有關編譯器的實現原理可參考[[Dragon Book]](bi01.html#bibli.dragonbook "Compilers: Principles, Techniques, & Tools")。 ### 習題 1、編寫遞歸函數求兩個正整數`a`和`b`的最大公約數（GCD，Greatest Common Divisor），使用Euclid算法： 1. 如果`a`除以`b`能整除，則最大公約數是`b`。 2. 否則，最大公約數等于`b`和`a%b`的最大公約數。 Euclid算法是很容易證明的，請讀者自己證明一下為什么這么算就能算出最大公約數。最后，修改你的程序使之適用于所有整數，而不僅僅是正整數。 2、編寫遞歸函數求Fibonacci數列的第`n`項，這個數列是這樣定義的： fib(0)=1 fib(1)=1 fib(n)=fib(n-1)+fib(n-2) 上面兩個看似毫不相干的問題之間卻有一個有意思的聯系： Lamé定理如果Euclid算法需要k步來計算兩個數的GCD，那么這兩個數之中較小的一個必然大于等于Fibonacci數列的第k項。感興趣的讀者可以參考[[SICP]](bi01.html#bibli.sicp "Structure and Interpretation of Computer Programs")第1.2節的簡略證明。 * * * [[8](#id2723765)] 例如很多編程書都會舉例的漢諾塔問題，本書不打算再重復這個題目了。