方悅
摘要:該文對比了循環(huán)、迭代與遞歸在概念、用法和性質(zhì)上的異同,以階乘和Fibonacci數(shù)列為例在c語言和匯編語言環(huán)境中進(jìn)行說明。
關(guān)鍵詞:循環(huán);迭代;遞歸;階乘;斐波那契數(shù)列
中圖分類號:TP311 文獻(xiàn)標(biāo)識碼:A
文章編號:1009-3044(2020)06-0055-03
任何復(fù)雜的事物都是由簡單的東西發(fā)展演變而來的,讓我們來從頭說起。這里最初始的概念是重復(fù)/反復(fù)(repeat),意思是一遍又一遍(again and again),是相對于“只做一遍”而言的。從強(qiáng)調(diào)“行為次數(shù)”到以“執(zhí)行路徑”為關(guān)注點(diǎn),我們引入了循環(huán)。循環(huán)(100p)的概念源自對環(huán)(cycle)這種物理形狀的邏輯抽象,用于形容運(yùn)行過程的周而復(fù)始。在計(jì)算機(jī)程序設(shè)計(jì)中,“循環(huán)”這一術(shù)語指的是一種專門的控制結(jié)構(gòu)。特征是重復(fù)執(zhí)行循環(huán)體中的語句,比一般情況下的順序執(zhí)行復(fù)雜一些,需要跳轉(zhuǎn)命令和條件判斷組合實(shí)現(xiàn)。循環(huán)側(cè)重于解決問題的過程,至于方法,主要有迭代和遞歸兩種。根據(jù)《簡明數(shù)學(xué)詞典》的定義,迭代(Iteration)指的是重復(fù)執(zhí)行一系列的運(yùn)算步驟,直到求得最終結(jié)果,特點(diǎn)是每一次迭代得到的結(jié)果都作為下一次迭代的初始值。在計(jì)算機(jī)領(lǐng)域,上述“一系列的運(yùn)算步驟”如果用“子程序”這個(gè)詞來代替就容易理解了。在此,迭代是用重復(fù)更替的方法,實(shí)現(xiàn)了更新變量數(shù)值的目的。有別于直接法(或者稱為一次解法),即一次性解決問題。講完了迭代,再來看遞歸。不過在談遞歸之前,引入另外一個(gè)詞:遞推。遞推與遞歸,一字之差,卻有不同,我們先看區(qū)別。從字面來簡單理解,遞推就是“以此類推”的意思。根據(jù)《中國中學(xué)教學(xué)百科全書·數(shù)學(xué)卷》定義,遞推是將復(fù)雜運(yùn)算化簡為若干步重復(fù)的簡單運(yùn)算。聽起來有一些抽象。其實(shí)遞推本是一個(gè)數(shù)學(xué)概念,源于數(shù)列。我們知道,如果數(shù)列{an}的第n項(xiàng)依靠其前一項(xiàng)或幾項(xiàng)確定,這種關(guān)系就叫遞推。例如:經(jīng)典的等差數(shù)列an=an-1+d、等比數(shù)列an=aa-1q、斐波那契數(shù)列(Fibonacci Sequence)an=an-1+an-2(n>=3,a1=1,a2=1),等。在計(jì)算機(jī)科學(xué)中,這種由初值求終值的遞推式理所當(dāng)然用迭代法來實(shí)現(xiàn)。
那么什么是遞歸呢?維基百科(Wikipedia)給出了這樣的詮釋:Recursion is the process of repeating items in a self-similarway.意思是說遞歸f或遞推)就是用自相似的方法進(jìn)行重復(fù)。何為“自相似”?根據(jù)《數(shù)學(xué)辭?!さ谖寰怼范x,當(dāng)該集的任一個(gè)局部放大適當(dāng)倍數(shù)后,它的形狀將會和其原來的整體相一致。如何做到這一點(diǎn)呢?在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中,遞歸通過在函數(shù)(子程序)的定義中使用函數(shù)(子程序)自身這種方法實(shí)現(xiàn)。后面的例子中我們將會看到,遞歸的求解包含“遞推”和“回歸”兩個(gè)過程。有趣的是,我們發(fā)現(xiàn)遞推和遞歸的英文都是Recursion,二者是不做區(qū)分的,都是指用相同的方法進(jìn)行自我更替。舉個(gè)大家熟悉的例子:從前有座山,山里有座廟,廟里有個(gè)和尚講故事,講的什么呢?從前有座山,山里有座廟,廟里有個(gè)和尚講故事,講的什么呢?從前有座山,山里有座廟,廟里有個(gè)和尚講故事,講的什么呢?……根據(jù)定義,這是典型的遞歸,同時(shí)也是一種遞推,在此過程中用到了迭代。在中文的語境,遞推暗含方向朝前(forward),而遞歸描述的是方向往回(back)。遞歸和遞推的共同點(diǎn)在于“遞”,強(qiáng)調(diào)使用相同算法更新迭代,所以二者在英文中是用分形來定義的。事實(shí)上,從嚴(yán)格的意義上講,遞歸除了有一般的自遞歸,還包括互遞歸?;ミf歸,是通過調(diào)用其他函數(shù)間接地調(diào)用自身的過程。此外,在C語言中,還有一個(gè)嵌套函數(shù)的概念。所謂嵌套函數(shù),指的是在某些情況下,可能需要將某函數(shù)作為另一函數(shù)的參數(shù)使用,這一函數(shù)就是嵌套函數(shù)。在一個(gè)函數(shù)被調(diào)用的過程中又調(diào)用另一個(gè)函數(shù),這就是函數(shù)的嵌套調(diào)用。特別的,如果是函數(shù)本身嵌套調(diào)用函數(shù)本身,那就是函數(shù)遞歸調(diào)用了。遞歸調(diào)用是嵌套調(diào)用的特殊情形,遞歸調(diào)用的本質(zhì)就是對同一個(gè)子程序(函數(shù))的嵌套調(diào)用。接下來我們以c語言和匯編語言條件下求階乘n!為例。
可以很清楚地看到,C語言中的循環(huán)在匯編環(huán)境下是用簡單的:比較指令cmp+跳轉(zhuǎn)指令(如jmp)的組合來實(shí)現(xiàn)的,這與我們下面談到的遞歸方法有所不同。
這里略微復(fù)雜一些,C語言中的遞歸調(diào)用factorial(n-1)是用call指令完成的。我們知道,call調(diào)用一個(gè)子程序的步驟是push+jump,即在堆棧中先用eax保存參數(shù)n-1,再跳轉(zhuǎn)到函數(shù)入口f013813C0)循環(huán)調(diào)用.factorial。此過程與迭代的相同之處是都含有計(jì)數(shù)器和參數(shù)的變化、并且都有出口條件保iiEN環(huán)次數(shù)有限,不同的地方是:迭代過程更新的是所求未知量,循環(huán)結(jié)束就能求得目標(biāo)結(jié)果;遞歸過程由兩部分組成,其分界線是到達(dá)函數(shù)出口(01381403)。前半部分壓棧操作(call)完成的只是參數(shù)的準(zhǔn)備工作(1、2、3、……、n),后半部分彈棧操作(retn)完成的才是實(shí)際計(jì)算(resuh=lx2x3x……×n)。從形式上可以看出,迭代一般只是“0型”的循環(huán)結(jié)構(gòu),而遞歸則是“8型”的循環(huán)結(jié)構(gòu),換句話說是由兩個(gè)循環(huán)連接組成的,見圖1:子程序的調(diào)用過程。
我們發(fā)現(xiàn),遞歸主要分為兩步,第一步是從目標(biāo)出發(fā)回溯到源頭,稱為回歸。第二步是從源頭出發(fā)逐步回代達(dá)到目標(biāo),稱為遞推。這就必須保存子程序的變量、參數(shù)與返回地址,使程序能夠返回到調(diào)用處繼續(xù)執(zhí)行。這一步是通過棧來實(shí)現(xiàn)的,做法是將函數(shù)的返回地址(也稱為“斷點(diǎn)”)即該函數(shù)下一條待執(zhí)行指令的地址壓棧。反復(fù)call(調(diào)用)子程序相當(dāng)于是“回歸”過程,多次執(zhí)行ret(返回)指令就相當(dāng)于“遞堆”過程。每一個(gè)call都會有一個(gè)ret與之對應(yīng),并且是某一級遞歸返回到調(diào)用它的那一級,而不是直接返回到main()函數(shù)中的初始調(diào)用部分。雖然每一級遞歸都有自己的變量和參數(shù),但是函數(shù)代碼并不會復(fù)制,變化的主要是棧區(qū)的數(shù)據(jù),下面我們用圖示來進(jìn)一步觀察和分析。
遞歸算法實(shí)質(zhì)就是一個(gè)函數(shù)不斷調(diào)用自身的過程,在調(diào)用過程中不斷地將局部變量、函數(shù)參數(shù)和返回地址壓人棧區(qū),當(dāng)返回時(shí)再將棧恢復(fù)到每一次調(diào)用前的狀態(tài),每一層調(diào)用過程棧幀中存放的返回地址都是相同的(013813F9)。在整個(gè)的返回階段,始終以EAX寄存器作為橋梁,反復(fù)和棧交換數(shù)據(jù),不斷地將中間結(jié)果保存在返回值中,從而實(shí)現(xiàn)參數(shù)的傳遞和結(jié)果的返回。
由此可見,遞歸確實(shí)是一種奇妙的思維方式。其優(yōu)點(diǎn)是很顯然的:容易理解,容易編程。不過,PeterDeutsch(彼得·道奇)曾說:To Iterate is Human,to Recurse,Divine.(用迭代的是人,用遞歸的,是神。)他想表達(dá)的意思是:遞歸雖好,能夠用對卻不容易。當(dāng)我們面對一個(gè)復(fù)雜問題的時(shí)候,應(yīng)當(dāng)想想能否將其轉(zhuǎn)化為較為簡單的同類問題呢?可以的話,就先轉(zhuǎn)換為簡單的同類問題來解決,然后再利用簡單的同類問題解法來解決復(fù)雜的同類問題,這就是遞歸思維方式的精髓所在。
遞歸的使用是有條件的。只有當(dāng)算法存在預(yù)期的收斂效果時(shí),采用遞歸算法才是可行的,否則,就不能使用遞歸算法。從數(shù)學(xué)角度講,有這幾種表達(dá)方式:函數(shù)具備收斂性=有確定的(或有限的)極限=極限是(確定的點(diǎn)或有限的數(shù)),對于計(jì)算機(jī)來說也一樣,要求約束條件必須收斂。簡而言之,循環(huán)次數(shù)是有限的,即有一個(gè)明確的邊界條件或臨界點(diǎn),作為遞歸出口。為做到這一點(diǎn),遞歸函數(shù)中必須包含終止遞歸的語句。通常遞歸函數(shù)會使用一個(gè)if條件語句或其他類似語句以便當(dāng)函數(shù)參數(shù)達(dá)到某個(gè)特定值(如上例的n=1)時(shí)結(jié)束遞歸調(diào)用。
遞歸和循環(huán)是兩種不同的解決問題的思路。單從算法設(shè)計(jì)上講,遞歸和循環(huán)并無優(yōu)劣之分。然而,在編程開發(fā)中,由于函數(shù)調(diào)用的開銷,遞歸常常會帶來性能問題,特別是在求解規(guī)模不確定的情況下;而循環(huán)因?yàn)闆]有函數(shù)調(diào)用開銷,所以效率會比遞歸高。我們以計(jì)算Fibonacci(斐波那契)函數(shù)為例來說明。
對于應(yīng)用程序而言,時(shí)間開銷和空間開銷是兩個(gè)重要的考察項(xiàng)目。從時(shí)間的角度來看,遞歸存在計(jì)算速度慢、執(zhí)行時(shí)間長的弊端,時(shí)間復(fù)雜度0(2n)呈現(xiàn)指數(shù)級的增長,相比于循環(huán)的線性變化0(n)要高得多,原因在于不必要的重復(fù)計(jì)算。下圖是n=5時(shí)的遞歸樹(recursion tree),可以看出虛線框中Fibonacci(2)的計(jì)算用到了三次,同樣的Fibonacci(3)的計(jì)算用到了兩次,顯然我們進(jìn)行了不少的重復(fù)運(yùn)算。不得不考慮到,當(dāng)n越大時(shí),情況越嚴(yán)重。
從空間的角度來看,循環(huán)使用的是堆空間,而遞歸使用的是??臻g。循環(huán)占用的內(nèi)存是一次性的,也就是O(1)的空間復(fù)雜度,而對于遞歸(不考慮尾遞歸優(yōu)化的情況),每次函數(shù)調(diào)用都要壓棧,那么空間復(fù)雜度是O(n),和遞歸次數(shù)呈線性關(guān)系。
綜上所述,循環(huán)、迭代與遞歸、遞推這幾個(gè)概念既有聯(lián)系,又有區(qū)別。它們是人們解決復(fù)雜問題的思想方法,無論是在閱讀還是在表達(dá)時(shí),不管是在學(xué)習(xí)還是在工作中,都應(yīng)做到準(zhǔn)確理解和正確使用。