免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

如果定義一個概念需要用到這個概念本身，我們稱它的定義是遞歸的（Recursive）。例如：

這只是一個玩笑，如果你在字典上看到這么一個詞條肯定要怒了。然而數(shù)學上確實有很多概念是用它自己來定義的，比如n的階乘（Factorial）是這樣定義的：n的階乘等于n乘以n-1的階乘。如果這樣就算定義完了，恐怕跟上面那個詞條有異曲同工之妙了：n-1的階乘是什么？是n-1乘以n-2的階乘。那n-2的階乘又是什么？這樣下去永遠也沒完。因此需要定義一個最關鍵的基礎條件（Base Case）：0的階乘等于1。

因此，3!=3*2!，2!=2*1!，1!=1*0!=1*1=1，正因為有了Base Case，才不會永遠沒完地數(shù)下去，知道了1!=1我們再反過來算回去，2!=2*1!=2*1=2，3!=3*2!=3*2=6。下面用程序來完成這一計算過程，我們要寫一個計算階乘的函數(shù)factorial，先把Base Case這種最簡單的情況寫進去：

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

如果參數(shù)n不是0應該return什么呢？根據(jù)定義，應該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這個函數(shù)居然可以自己調(diào)用自己？是的。自己直接或間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)。這里的factorial是直接調(diào)用自己，有些時候函數(shù)A調(diào)用函數(shù)B，函數(shù)B又調(diào)用函數(shù)A，也就是函數(shù)A間接調(diào)用自己，這也是遞歸函數(shù)。如果你覺得迷惑，可以把factorial(n-1)這一步看成是在調(diào)用另一個函數(shù)－－另一個有著相同函數(shù)名和相同代碼的函數(shù)，調(diào)用它就是跳到它的代碼里執(zhí)行，然后再返回factorial(n-1)這個調(diào)用的下一步繼續(xù)執(zhí)行。我們以factorial(3)為例分析整個調(diào)用過程，如下圖所示：

圖 5.2. factorial(3)的調(diào)用過程

圖中用實線箭頭表示調(diào)用，用虛線箭頭表示返回，右側(cè)的框表示在調(diào)用和返回過程中各層函數(shù)調(diào)用的存儲空間變化情況。

我們看上圖右側(cè)存儲空間的變化過程，隨著函數(shù)調(diào)用的層層深入，存儲空間的一端逐漸增長，然后隨著函數(shù)調(diào)用的層層返回，存儲空間的這一端又逐漸縮短，并且每次訪問參數(shù)和局部變量時只能訪問這一端的存儲單元，而不能訪問內(nèi)部的存儲單元，比如當factorial(2)的存儲空間位于末端時，只能訪問它的參數(shù)和局部變量，而不能訪問factorial(3)和main()的參數(shù)和局部變量。具有這種性質(zhì)的數(shù)據(jù)結(jié)構(gòu)稱為堆?；驐＃⊿tack），隨著函數(shù)調(diào)用和返回而不斷變化的這一端稱為棧頂，每個函數(shù)調(diào)用的參數(shù)和局部變量的存儲空間（上圖的每個小方框）稱為一個棧幀（Stack Frame）。操作系統(tǒng)為程序的運行預留了一塊?？臻g，函數(shù)調(diào)用時就在這個?？臻g里分配棧幀，函數(shù)返回時就釋放棧幀。

在寫一個遞歸函數(shù)時，你如何證明它是正確的？像上面那樣跟蹤函數(shù)的調(diào)用和返回過程算是一種辦法，但只是factorial(3)就已經(jīng)這么麻煩了，如果是factorial(100)呢？雖然我們已經(jīng)證明了factorial(3)是正確的，因為它跟我們用數(shù)學公式計算的過程一樣，結(jié)果也一樣，但這不能代替factorial(100)的證明，你怎么辦？別的函數(shù)你可以跟蹤它的調(diào)用過程去證明它的正確性，因為每個函數(shù)只調(diào)用一次就返回了，但是對于遞歸函數(shù)，這么跟下去只會跟得你頭都大了。事實上并不是每個函數(shù)調(diào)用都需要鉆進去看的。我們在調(diào)用printf時沒有鉆進去看它是怎么打印的，我們只是相信它能打印，能正確完成它的工作，然后就繼續(xù)寫下面的代碼了。在上一節(jié)中，我們寫了distance和area函數(shù)，然后立刻測試證明了這兩個函數(shù)是正確的，然后我們寫area_point時調(diào)用了這兩個函數(shù)：

return area(distance(x1, y1, x2, y2));

在寫這一句的時候，我們需要鉆進distance和area函數(shù)中去走一趟才知道我們調(diào)用得是否正確嗎？不需要，因為我們已經(jīng)相信這兩個函數(shù)能正確工作了，也就是相信把坐標傳給distance它就能返回正確的距離，把半徑傳給area它就能返回正確的面積，因此調(diào)用它們?nèi)ネ瓿闪硗庖患ぷ饕矐撌钦_的。這種“相信”稱為Leap of Faith，首先相信一些結(jié)論，然后再用它們?nèi)プC明另外一些結(jié)論。

在寫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)的結(jié)果。當然這有點奇怪：我們還沒寫完factorial這個函數(shù)，憑什么要相信factorial(n-1)是正確的？可Leap of Faith本身就是Leap（跳躍）的，不是嗎？如果你相信你正在寫的遞歸函數(shù)是正確的，并調(diào)用它，然后在此基礎上寫完這個遞歸函數(shù)，那么它就會是正確的，從而值得你相信它正確。

這么說好像有點兒玄，我們從數(shù)學上嚴格證明一下factorial函數(shù)的正確性。剛才說了，factorial(n)的正確性依賴于factorial(n-1)的正確性，只要后者正確，在后者的結(jié)果上乘個n返回這一步顯然也沒有疑問，那么我們的函數(shù)實現(xiàn)就是正確的。因此要證明factorial(n)的正確性就是要證明factorial(n-1)的正確性，同理，要證明factorial(n-1)的正確性就是要證明factorial(n-2)的正確性，依此類推下去，最后是：要證明factorial(1)的正確性就是要證明factorial(0)的正確性。而factorial(0)的正確性不依賴于別的函數(shù)調(diào)用，它就是程序中的一個小的分支return 1;，這個1是我們根據(jù)階乘的定義寫的，肯定是正確的，因此factorial(1)的實現(xiàn)是正確的，因此factorial(2)也正確，依此類推，最后factorial(n)也是正確的。其實這就是在中學時學的數(shù)學歸納法（Mathematical Induction），用數(shù)學歸納法來證明只需要證明兩點：Base Case正確，遞推關系正確。寫遞歸函數(shù)時一定要記得寫B(tài)ase Case，否則即使遞推關系正確，整個函數(shù)也不正確。如果factorial函數(shù)漏掉了Base Case：

int factorial(int n){	int recurse = factorial(n-1);	int result = n * recurse;	return result;}

那么這個函數(shù)就會永遠調(diào)用下去，直到操作系統(tǒng)為程序預留的?？臻g耗盡程序崩潰（段錯誤）為止，這稱為無窮遞歸（Infinite recursion）。

到目前為止我們只學習了全部C語法的一個小的子集，但是現(xiàn)在應該告訴你：這個子集是完備的，它本身就可以作為一門編程語言了，以后還要學習很多C語言特性，但全部都可以用已經(jīng)學過的這些特性來代替。也就是說，以后要學的C語言特性會使代碼寫起來更加方便，但不是必不可少的，現(xiàn)在學的這些已經(jīng)完全覆蓋了第 1 節(jié) “程序和編程語言”講的五種基本指令了。有的讀者會說循環(huán)還沒講到呢，是的，循環(huán)在下一章才講，但有一個重要的結(jié)論就是遞歸和循環(huán)是等價的，用循環(huán)能做的事用遞歸都能做，反之亦然，事實上有的編程語言（比如某些LISP實現(xiàn)）只有遞歸而沒有循環(huán)。計算機指令能做的所有事情就是數(shù)據(jù)存取、運算、測試和分支、循環(huán)（或遞歸），在計算機上運行高級語言寫的程序最終也要翻譯成指令，指令做不到的事情高級語言寫的程序肯定也做不到，雖然高級語言有豐富的語法特性，但也只是比指令寫起來更方便而已，能做的事情是一樣多的。那么，為什么計算機要設計成這樣？在設計時怎么想到計算機應該具備這幾樣功能，而不是更多或更少的功能？這些要歸功于早期的計算機科學家，例如Alan Turing，他們在計算機還沒有誕生的年代就從數(shù)學理論上為計算機的設計指明了方向。有興趣的讀者可以參考有關計算理論的教材，例如[IATLC]。

遞歸絕不只是為解決一些奇技淫巧的數(shù)學題^[8]而想出來的招，它是計算機的精髓所在，也是編程語言的精髓所在。我們學習在C的語法時已經(jīng)看到很多遞歸定義了，例如在第 1 節(jié) “數(shù)學函數(shù)”講過的語法規(guī)則中，“表達式”就是遞歸定義的：

再比如在第 1 節(jié) “if語句”講過的語規(guī)則中，“語句”也是遞歸定義的：

可見編譯器在解析我們寫的程序時一定也用了大量的遞歸，有關編譯器的實現(xiàn)原理可參考[Dragon Book]。