[6] 分支、循環與遞歸

03-02

上一節：《多文件工程》

首先我們看看如何列印一位數，程序如下：

int putchar(int);void pd(int n){ int p = 0 + n; putchar(p);}int main(){ int a = 8; pd(a); return 0;}

說明：

函數類型如果是void，表明函數沒有返回值（這樣的函數被稱為過程）
「入門問題」講過0是字元0在ASCII碼錶中的序號，又因為字元0到字元9是順序排列的，所以0的序號加一就是1的序號，以此類推。

單詞解釋：

void : 空、虛無

但這個程序只能列印一位數，如果要列印多位數，就要用到分支語法了。

聰明人在做事的時候，能根據情況的不同來作出不同的選擇，聰明人寫的程序也可以。在不同的情況下，讓同樣的程序產生不同的結果，這需要用到分支語法。最常見的分支語法是if-else語法，形式如下：

if (變數) (一條語句，變數為真時運行)

或者

if (變數) { (若干條語句，變數為真時運行)}

或者

if (變數) { (若干條語句，變數為真時運行)} else { (若干條語句，變數為假時運行)}

所謂變數為真，是指變數不等於0。所謂變數為假，是指變數等於0。

題目：在程序中設置一個整數變數n，當n是偶數是列印字元E，當n是奇數時列印字元O。

解釋：「列印」是指顯示在屏幕上，由於早先計算機的輸出設備是電傳印表機，因此術語被保留了下來。偶數的英文是even，所以列印字母E，奇數的英文是odd，所以列印字母O。

判斷一個整數是偶數還是奇數，方法是計算整數除以2的餘數。如果餘數是0，那麼這個數就是偶數；如果餘數是1，那麼就是奇數。程序如下：

int putchar(int);int main(){ int n = 32; int x = n % 2; if (x) putchar(O); int y = (x == 0); if (y) putchar(E); return 0;}

注意：千萬不要把x == 0寫成x = 0，一個等號表示變數賦值，兩個等號是比較運算

讓我們一步步分析一下：

x = 32 % 2所以x等於0，於是if (x) putchar(O)等價於if (0) putchar(O)，因為if(...)的變數為假（等於0），所以後面的putchar(O)是不會被執行的。

程序繼續執行下一條語句y = (x == 0)，相當於y = (0 == 0)，而==是一個比較運算符，當左右兩邊的整數相等時，這個比較會產生一個結果1（如果兩邊不相等，比較的結果是0——「入門問題」講過的）。所以y = (0 == 0)等價於y = 1。下面的if (y) putchar(E)相當於if (1) putchar(E)，因為if(...)的變數為真（不等於0），所以接下來會繼續執行後面的putchar(E)，屏幕上就會列印出字元E了。

注意上面這個程序是為了解釋if-else語法的原理才故意寫得這麼不直觀的，這道題目直觀的寫法是：

int putchar(int);int main(){ int n = 32; if (n % 2 == 0) putchar(E); else putchar(O); return 0;}

或者我們可以加上大括弧：

int putchar(int);int main(){ int n = 32; if (n % 2 == 0) { putchar(e); putchar(v); putchar(e); putchar(n); } else { putchar(o); putchar(d); putchar(d); } return 0;}

當if-else包含多條語句時，大括弧是不能省略的。否則程序執行的順序會跟你預想的不一樣，不信的話可以試試去掉上一個程序的大括弧，看看運行的結果是否如你所料。

有了if-else語法，我們現在可以嘗試列印多位整數了。假設要列印的整數不超過4位，程序如下：

int putchar(int);void pd(int);void pu(int n){ if (n >= 1000) { pd(n / 1000); n = n % 1000; } if (n >= 100) { pd(n / 100); n = n % 100; } if (n >= 10) { pd(n / 10); n = n % 10; } pd(n);}int main(){ int a = 3579; pu(a); return 0;}

說明：

pd函數的實現就沒寫了，請參照上一講「多文件工程」的內容進行補全
當n=3579時，n/1000的結果是3579÷1000的商取整，也就是3579/1000的結果是3。n%1000的結果是3579÷1000的餘數，所以3579%1000結果是579。語句n = n % 1000等價於n = 579，n的值就從3579變成了579
注意函數pu沒法顯示負數

然而，上面的程序看起來挺「丑」的，可以想像如果我們要列印8位數，那我們需要從n >= 10000000開始寫，但每一個if里的內容看起來又是差不多的。有沒有方法可以像下面流程圖描述的這樣，讓程序變得「優雅」呢？

答案是可以！C語言提供了定義行(háng)號和跳轉到行號的方法：

定義行號：行號: 行號可以隨意命名
跳轉到行號：goto 行號（goto是英文go和to兩個單詞拼接而成）

下面就是使用了行號和goto的更加優雅的列印整數的程序：

int putchar(int);void pd(int); void pu(int n){ int b = 10000000;r: if (n >= b) { pd(n / b); n = n % b; } if (n < 10) { pd(n); return; } b = b / 10; goto r;}int main(){ int a = 357924; pu(a); return 0;}

說明：

流程圖中的「終止」，可以用return;語句實現。因為pu函數沒有返回值，所以return只能單獨使用。
C語言只允許在同一個函數內跳轉，想goto到別的函數內的行號位置是不行的。
如果不在合適的時機終止程序，那麼程序就會永遠運行下去，這種情況被稱為死循環。不過即使出現死循環也不要緊張，操作系統可以從外圍關閉這個程序（比如點窗口右上角的叉叉），死循環的程序除了讓CPU稍微發燙以外，對電腦也沒有什麼影響。

我們還可以不從流程圖的角度，而是從定義問題的角度來解決列印整數的問題，並且不必考慮整數的位數：

把列印整數n的過程定義為：1. 如果n小於10則調用pd(n)列印n2. 列印整數n/103. 列印整數n%10

例如你在教計算機用上面的方法列印135，計算機會試著列印13和列印5，由於5小於10，所以計算機是知道怎麼列印5的，但別著急，計算機先要列印13然後才能列印5。但它目前不清楚怎麼列印13，它只好繼續把列印13的任務轉化成列印1和列印3這兩個任務，這兩個任務計算機知道怎麼完成（調用pd函數）。最終計算機會列印出1和3，相當於完成了列印13的任務，然後列印出5，屏幕上就會顯示出135了。

程序如下：

int putchar(int);void pd(int);void pu(int n){ if (n < 10) pd(n); else { pu(n / 10); pu(n % 10); }}int main(){ int a = 357924; pu(a); return 0;}

像這樣在函數實現中調用自身的寫法叫做遞歸，目前你不用了解C語言是怎樣實現遞歸的（後續會詳細講解），只用知道遞歸允許我們把一個大目標分解成小目標、小目標分解成更小的目標…最終分解成我們可以解決的目標。只要分解目標的方式從理論上是正確的，那麼程序運行的結果就一定是正確的。

下一講我們會講解循環的三種模式。在這之前請考慮下列問題：

如何計算1+2+3+...+100的值？
如何計算1*2*3*...*10的值？
如何計算1+3+5+...+101的值？
如何計算1*1+2*2+3*3+...+10*10的值？

請嘗試分別用goto和遞歸解決一遍，然後看goto和遞歸算出來的答案是否一樣。（如果在看下一講之前你能全都做出來，那恭喜你很適合學編程，加油吧）

下一節：《循環的模式》