用匯編語言剖析遞歸算法的內(nèi)在機理

火善棟 楊旭東

（1.重慶三峽學(xué)院，重慶萬州 404000）

（2.重慶安全技術(shù)職業(yè)學(xué)院，重慶萬州 404000）

0 引 言

遞歸算法是計算機領(lǐng)域中一個很重要的算法，通過遞歸算法可以使很復(fù)雜的問題變得很容易解決，例如著名的漢諾塔問題，假若不采用遞歸算法的話可能無法解決，還有數(shù)據(jù)結(jié)構(gòu)中樹和圖的遍歷，通過采用遞歸算法從而使問題變得非常容易，當(dāng)然遞歸算法在很多地方也有著很廣泛的應(yīng)用.

遞歸算法雖然編寫起來比較容易，但在對遞歸算法的理解上，很多人卻感到很抽象，在學(xué)習(xí)過程中往往對這類問題的執(zhí)行過程不了解，對遞歸問題的認(rèn)識不清楚，所以難以寫出正確的遞歸程序，另外，在對遞歸算法的執(zhí)行效率以及空間復(fù)雜度上很多人更是感到難以理解.這其中一個很重要的原因就是對遞歸算法的內(nèi)在機理沒有搞清楚，對遞歸算法中函數(shù)如何反復(fù)調(diào)用以及參數(shù)如何進行傳遞沒有理解透徹.

由于高級語言把程序運行的內(nèi)部細(xì)節(jié)都透明化了，所以想通過高級語言理解遞歸算法的內(nèi)在運行機理是不可能的，但匯編語言是一門低級語言，其實質(zhì)也是機器語言一對一的符號化，是指令級的語言，雖然通過匯編語言編寫程序代碼費時費力，但通過匯編語言可以看出程序運行的每一個細(xì)節(jié).因此，這對理解遞歸算法無疑是一個很好的工具.

1 實例分析

本文通過一個很簡單的遞歸算法的例子“斐波那契（Fibonacci）數(shù)列”來具體剖析遞歸算法的內(nèi)在運行機理，從而加深對遞歸算法的理解，進而幫助讀者更好地用好遞歸算法.

【問題】編寫計算斐波那契（Fibonacci）數(shù)列的第n項函數(shù)fib（n）.

斐波那契數(shù)列為：0、1、1、2、3、……，即：

fib(0)=0;

fib(1)=1;

fib(n)=fib(n-1)+fib(n-2) （當(dāng)n>1時）

寫成遞歸函數(shù)通常是：

為了使這個簡單的遞歸算法更具有代表性以及分析在遞歸算法內(nèi)部參數(shù)是如何傳遞的，本文把上述代碼改寫成“表1”左面所示的形式（C語言代碼）.

“表 1”是“斐波那契（Fibonacci）數(shù)列”遞歸算法的C語言實現(xiàn)代碼以及對應(yīng)的反匯編代碼，“圖 1”是通過分析反匯編代碼得出的該算法的堆棧變化示意圖.

從下面這段反匯編代碼中可以看出，C程序中的遞歸函數(shù)對應(yīng)的反匯編代碼是一個遠(yuǎn)調(diào)用子過程，其整個調(diào)用過程的基本情況和執(zhí)行過程如下：

1.1 進行函數(shù)調(diào)用時首先將函數(shù)的參數(shù)（形參）壓入堆棧（在C語言中壓入的順序是從右到左，由于本實例只有一個參數(shù)，所以沒有反應(yīng)出來），本例是通過SI寄存器來實現(xiàn)這一過程的.

1.2 將函數(shù)的返回地址即該函數(shù)下一條將要執(zhí)行指令的地址壓入堆棧（由于本實例是遠(yuǎn)調(diào)用，所以將CS和IP的值壓入了堆棧）同時修改CS和IP寄存器的值，跳轉(zhuǎn)到要執(zhí)行指令的起始位置，從而實現(xiàn)了函數(shù)的調(diào)用.

1.3 將BP的值壓入堆棧保護BP寄存器的值為以后恢復(fù)棧頂指針（SP）做準(zhǔn)備，然后將SP的值賦給BP，再通過BP訪問堆棧中傳入?yún)?shù)和函數(shù)體內(nèi)部定義的局部變量.

1.4 將函數(shù)體內(nèi)部定義的局部變量壓入堆棧，本實例定義了三個局部變量，但只壓入了兩個，這個過程是通過SUB SP 4來實現(xiàn)的，有一個作為返回值沒有壓入.

1.5 為了保證函數(shù)調(diào)用的透明性，將其調(diào)用過程中要用到寄存器的值（SI，DI）壓入堆棧.

1.6 以上過程為函數(shù)體代碼的執(zhí)行作好了準(zhǔn)備，緊接的過程就是通過BP來實現(xiàn)函數(shù)參數(shù)的傳遞，并將中間結(jié)果保存在局部變量中，這一過程全部是通過對堆棧的操作來實現(xiàn)的.

表1 斐波那契數(shù)列遞歸調(diào)用C語言與匯編代碼對比表

圖1 堆棧變化示意圖

1.7 每一次函數(shù)調(diào)用結(jié)束之后，恢復(fù)中間寄存器（本實例是SI，DI）以及SP，BP的值，本實例通過POP DI，POP SI，MOV SP，BP以POP BP來實現(xiàn)的.返回結(jié)果最后保存在AX寄存中，在本實例中函數(shù)體內(nèi)部的遞歸調(diào)用也是通過AX來實現(xiàn)參數(shù)傳遞的.另外由于主函數(shù)體的調(diào)用是一個FAR調(diào)用，而函數(shù)體內(nèi)部調(diào)用是一個near調(diào)用，為了實現(xiàn)遞歸調(diào)用過程的統(tǒng)一性，本實例通過PUSH CS和這一條指令來實現(xiàn)了遞歸調(diào)用的一致性工作，從而保證了代碼執(zhí)行的高效性.

1.8 函數(shù)調(diào)用結(jié)束之后，SP和BP基本恢復(fù)為調(diào)用前的初始狀態(tài)，但函數(shù)在執(zhí)行retf指令之后，堆棧還沒有完全清空，里面還保留著傳入?yún)?shù)的值，所以本實例通過POP CX這一指令來實現(xiàn)了清棧工作（這一情況會隨傳入?yún)?shù)個數(shù)的不同而有不同）.

總之，函數(shù)在執(zhí)行調(diào)用之后，堆棧完全恢復(fù)為調(diào)用前的最初始狀態(tài)，只是結(jié)果保存在AX寄存器中，進而實現(xiàn)了函數(shù)調(diào)用的透明性.

筆者認(rèn)為，理解遞歸調(diào)用的一個重要難點就是要搞清楚在遞歸調(diào)用內(nèi)部是如何進行參數(shù)傳遞的，以及返回值是如何保存的.通過對以上反匯編代碼的分析可以看出，AX寄存器起到了一個很重要的作用，以AX寄存器作為橋梁，不斷地和堆棧交換數(shù)據(jù)，不斷地將中間結(jié)果保存在AX寄存器中，從而很輕松地實現(xiàn)了參數(shù)的傳遞和結(jié)果的保存.

通過以上分析，可以得出“斐波那契（Fibonacci）數(shù)列”遞歸算法（n=5）的具體執(zhí)行過程，如圖 2所示：

圖2 遞歸調(diào)用示意圖

從圖二中可以看出，“斐波那契（Fibonacci）數(shù)列”遞歸算法的遞歸調(diào)用過程非常像一顆二叉樹中的前序遍歷，這是由于遞歸函數(shù)體fibo（n）中有兩個函數(shù)體fibo（n-1）和fibo（n-2）所造成的，由此可以推出當(dāng)遞歸函數(shù)體有三個甚至n個函數(shù)體的情況，當(dāng)然當(dāng)遞歸函數(shù)體只有一個函數(shù)體時，這是一種最簡單的遞歸調(diào)用形式.

2 結(jié) 論

遞歸算法實質(zhì)就是一個函數(shù)體不斷調(diào)用自身的過程，在調(diào)用的過程中不斷地將參數(shù)、返回地址以及局部變量壓入堆棧，當(dāng)返回時又將堆?；謴?fù)到每一次調(diào)用前的狀態(tài).在整個調(diào)用過程中，始終以AX或EAX寄存器作為橋梁，不斷地和堆棧交換數(shù)據(jù)，不斷地將中間結(jié)果保存在AX或EAX寄存器中，從而順利地實現(xiàn)了參數(shù)的傳遞和結(jié)果的返回.另外，遞歸函數(shù)在執(zhí)行遞歸調(diào)用的過程，要不斷地執(zhí)行進棧和出棧操作，所以執(zhí)行效率相對要低一些；同時，遞歸算法內(nèi)存的消耗也主要是用在堆棧的花銷上，但堆棧對內(nèi)存的占用是一個不斷變化的動態(tài)過程，因此，其最大占用內(nèi)存是由遞歸調(diào)用的最深層次決定的.

就對遞歸算法的理解而言，我們可以將其視為一個樹形結(jié)構(gòu)，當(dāng)遞歸函數(shù)體中有兩個遞歸函數(shù)時，其執(zhí)行過程類似于二叉樹的前序遍歷.推而廣之，當(dāng)遞歸函數(shù)體中有n個遞歸函數(shù)時，就相當(dāng)于這顆樹中有n個分枝，也就是形式上的“n叉樹”.

[1]譚文等.天書夜讀：從匯編語言到 Windows內(nèi)核編程[M].北京：電子工業(yè)出版社，2008，10.

[2]火善棟.通過匯編語言理解函數(shù)調(diào)用的內(nèi)在機理[J].計算機時代，2010（7）.

[3]呂鳳翥.C++語言程序設(shè)計[M].北京：清華大學(xué)出版社，2003，7.

[4]卜艷萍.匯編語言程序設(shè)計教程：第二版[M].北京：清華大學(xué)出版社，2008，7.

[5]邵桂芳，李剛，張小川.多媒體技術(shù)在匯編語言程序設(shè)計課程中的應(yīng)用[J].重慶工學(xué)院學(xué)報：自然科學(xué)版，2007（11）.

[6]楊隆平.SQL語言在VB中的優(yōu)化應(yīng)用[J].重慶三峽學(xué)院學(xué)報，2010（3）.