摘要：本文根據(jù)作者多年的教學(xué)和軟件開發(fā)經(jīng)驗(yàn)，從遞歸的定義出發(fā)，通過對一個(gè)匯編語言遞歸子程序的剖析，詳細(xì)分析了遞歸調(diào)用在類推和返回過程中堆棧的變化，從匯編語言的角度討論了遞歸的本質(zhì)和特點(diǎn)，這對學(xué)生正確理解和應(yīng)用遞歸解決實(shí)際問題有很好的參考價(jià)值。

關(guān)鍵詞：匯編語言；遞歸；堆棧；子程序；嵌套調(diào)用

中圖分類號：G642文獻(xiàn)標(biāo)識(shí)碼：B

匯編語言是一種低級語言，是機(jī)器指令的符號化表示，描述了機(jī)器最終要執(zhí)行的指令序列，也是人與機(jī)器最直接的溝通語言。高級語言大都編譯為匯編指令，最終轉(zhuǎn)化為機(jī)器指令得以執(zhí)行，從編譯器的角度，也就是從匯編語言的角度討論遞歸，既有助于透徹的理解高級語言的核心原理，又能明晰程序內(nèi)部的執(zhí)行過程，更重要的是能夠獲得直接從底層分析問題解決問題的能力，從而真正理解和掌握遞歸算法。

1遞歸的本質(zhì)

一個(gè)對象部分地由它自己組成，或者是按它自己定義，則稱為是遞歸的。遞歸是一種描述問題的方法，或稱算法。遞歸的思想可以簡單地描述為“自己調(diào)用自己”。例如用如下方法定義階乘：

n!=n*(n-1)!(n>1)

可以看出是用階乘定義階乘，這種自己定義自己的方法稱為遞歸定義。

又如，數(shù)學(xué)中對自然數(shù)的定義：

(1)1是自然數(shù)；

(2) 自然數(shù)的后繼是自然數(shù)；

也是典型的遞歸定義，遞歸的能力在于有可能用有限的語句來定義對象的無限集合。采用遞歸算法解決問題必須符合以下三個(gè)條件：(1)可以把要解決的問題轉(zhuǎn)化為一個(gè)新的問題，而這個(gè)新問題的解決方法與原來的解決方法相同，只是所處理的對象有規(guī)律地遞增或遞減；(2)可以使用這個(gè)轉(zhuǎn)化過程使問題得到解決；(3)必須有一個(gè)明確的結(jié)束遞歸的條件。即我們在編寫遞歸程序時(shí)要考慮以下兩個(gè)問題：

① 遞歸的形式；②遞歸的結(jié)束條件。

如果沒有第一點(diǎn)，就不可能通過不斷地遞歸接近于目標(biāo)。如果沒有第二個(gè)條件，遞歸就不會(huì)結(jié)束，一直會(huì)遞歸到內(nèi)存空間用完為止。遞歸調(diào)用分兩個(gè)階段：

第一階段：遞推。將原問題不斷分解為新的子問題，逐漸從未知向已知推進(jìn)，最終達(dá)到已知條件，即遞歸結(jié)束的條件，這時(shí)遞推階段結(jié)束。例如求4!可以這樣分解：

4! = 4 × 3! → 3! =3 × 2! → 2! = 2 × 1! → 1! = 1 × 0! → 0! = 1

第二階段：回歸。從已知條件出發(fā)，按照遞推的逆過程，逐一求值回歸，最后達(dá)到遞歸的開始處，結(jié)束回歸階段，完成遞歸調(diào)用。例如求4!的回歸階段如下：

4! = 4 × 3! = 24 ←3! =3 × 2! = 6 ← 2! = 2 × 1! =2 ← 1! = 1 × 0! = 1 ← 0! = 1

遞歸分為直接遞歸和間接遞歸，如果一個(gè)子程序(函數(shù))直接調(diào)用它自身，即直接遞歸調(diào)用；如果一個(gè)子程序(函數(shù))間接調(diào)用它自身，即間接遞歸。具有遞歸調(diào)用的子程序(函數(shù))稱為遞歸子程序(函數(shù))。遞歸調(diào)用是嵌套調(diào)用的特殊情形，遞歸調(diào)用的本質(zhì)即是對同一個(gè)子程序(函數(shù))的嵌套調(diào)用。在高級語句中當(dāng)遞歸調(diào)用發(fā)生時(shí)，系統(tǒng)自動(dòng)將函數(shù)中當(dāng)前的變量和形參暫時(shí)保留起來。在新一輪的調(diào)用過程中，系統(tǒng)為新調(diào)用的函數(shù)所用的變量和形參開辟另外的存儲(chǔ)單元(內(nèi)存單元)，這樣，每次調(diào)用函數(shù)所使用的同名變量在不同的內(nèi)存空間，遞歸調(diào)用的層次越多，同名變量占用的存儲(chǔ)單元也就越多，當(dāng)遞歸返回時(shí)，系統(tǒng)將釋放本次調(diào)用時(shí)所占用的內(nèi)存空間，程序流程返回到上一層的調(diào)用點(diǎn)，同時(shí)取得當(dāng)初進(jìn)入該函數(shù)時(shí)函數(shù)中的變量和形參所占用的內(nèi)存空間的數(shù)據(jù)。在匯編語言中也非常類似，在遞歸調(diào)用返回前，相當(dāng)于有多個(gè)相同的子程序同時(shí)在運(yùn)行，但分別屬于不同的子程序空間，有多個(gè)同名的變量或寄存器同時(shí)出現(xiàn)，但互不影響。匯編語言是一種低級語言，通過對匯編語言遞歸子程序的調(diào)試，可以清晰地觀察堆棧的變化及子程序返回的過程，這對理解遞歸調(diào)用的本質(zhì)很有幫助。

2從匯編語言的角度剖析遞歸

下面我們通過剖析一個(gè)匯編語言遞歸子程序的調(diào)用和返回過程中堆棧的變化，讓學(xué)生真正掌握遞歸調(diào)用的本質(zhì)。例1：以下遞歸子程序的功能是實(shí)現(xiàn)將AX寄存器中的值以十六進(jìn)制形式輸出，程序代碼如下：

disp proc near ；子程序定義開始

cmp ax，15

jbe next

push ax

push bp

mov bp，sp

mov bx，[bp+2]

and bx.0fh

mov [bp+2]，bx

pop bp

mov cl，4

shr ax，cl

call disp ；遞歸調(diào)用

IP2:pop ax ；返回地址標(biāo)記， 設(shè)標(biāo)號IP2在代碼段的偏移為123H

next:add al，30h；以下指令實(shí)現(xiàn)將AL的值以十六進(jìn)制形式輸出

cmp al，3ah

jb output

add al，7

output:mov dl，al

mov ah，2

int 21h

ret

disp endp ；子程序定義結(jié)束

設(shè)在主調(diào)程序中，有如下調(diào)用：

mov ax，5678h

call disp

IP1:…… ；設(shè)標(biāo)號IP1在代碼段的偏移為200H

本程序中遞歸子程序采用約定寄存器法傳遞參數(shù)。子程序的算法非常簡單，即在遞推的過程中不斷將AX寄存器中的值除以16(此時(shí)的余數(shù)是十六進(jìn)制數(shù)的最低位，不能馬上輸出)，直到AX中的值小于16為止，然后在遞歸返回的過程中輸出相應(yīng)的余數(shù)。我們首先來分析在遞歸調(diào)用的第一階段，即遞推的過程中堆棧的變化情況，設(shè)堆棧段的大小為100H，即當(dāng)堆棧為空時(shí)SP=100H，如圖1所示：

在主程序中首先將主程序中的返回地址IP1(設(shè)IP1的偏移為200H)壓入堆棧，然后轉(zhuǎn)到遞歸子程序disp中執(zhí)行，將AX(值為5678H)的值壓入堆棧，并通過堆棧的間接尋址將AX的最低4位的值08H(即第一個(gè)余數(shù))存儲(chǔ)到堆棧中(修改了堆棧中原來存儲(chǔ)的AX的值)，再一次調(diào)用遞歸子程序disp，并將返回地址IP2(設(shè)IP2的偏移為123H)壓入堆棧，此時(shí)堆棧中情況如圖1中的a所示，執(zhí)行過程中再將AX(值567H)的值壓入堆棧，并通過堆棧的間接尋址將AX的最低4位的值07H(即第二個(gè)余數(shù))存儲(chǔ)到堆棧中(修改了堆棧中原來存儲(chǔ)的AX的值)，再一次調(diào)用遞歸子程序disp，以此類推，多次將同一個(gè)返回地址(IP2的值)壓入堆棧進(jìn)行保護(hù)，當(dāng)AX的值為05H時(shí)，此時(shí)AX已小于16，滿足條件轉(zhuǎn)移指令的條件，跳轉(zhuǎn)到標(biāo)號next處執(zhí)行，首先輸出5，執(zhí)行到ret指令時(shí)，從棧頂彈出一個(gè)字送IP，即將IP2值(即IP2的偏移，設(shè)為123H)送指令計(jì)數(shù)器IP，程序流程再次轉(zhuǎn)到IP2處執(zhí)行，執(zhí)行出棧指令POPＡＸ，將新的棧頂?shù)闹?6H，送AX，接著順序執(zhí)行標(biāo)號next處的指令，輸出6，然后繼續(xù)遞歸返回，分別輸出7和8，再返回到主程序IP1處，執(zhí)行主程序中的其他指令，如圖2所示。

通過這個(gè)簡單的例子，我們可以很清楚地看到堆棧的變化情況，特別是返回地址入棧的情況，這對我們理解子程序調(diào)用和返回的工作原理很有幫助，進(jìn)而幫助我們理解子程序的嵌套調(diào)用和子程序的遞歸調(diào)用。使學(xué)生真正理解了遞歸調(diào)用的本質(zhì)及遞歸調(diào)用的類推和回歸的過程，并且能夠真正理解在遞歸子程序中，由于遞歸調(diào)用，遞歸子程序被分解為兩部分，其中一部分是遞歸調(diào)用的遞推的過程中執(zhí)行，另一部分是在遞歸返回的過程執(zhí)行的。

3結(jié)論

遞歸算法結(jié)構(gòu)簡練、清晰，可讀性強(qiáng)，而且它的正確性容易得到證明，但掌握它并不容易。理解遞歸的本質(zhì)是對同一個(gè)子程序的嵌套調(diào)用，是真正掌握遞歸的一個(gè)關(guān)鍵。從遞歸調(diào)用的定義出發(fā)，通過對一個(gè)匯編語言遞歸子程序的剖析，來詳細(xì)分析遞歸調(diào)用在類推和返回過程中堆棧的變化，可以使學(xué)生能夠真正理解遞歸調(diào)用的本質(zhì)，從而能夠正確理解和應(yīng)用遞歸解決實(shí)際問題。

參考文獻(xiàn)

[1] 沈美明，溫冬嬋. IBM-PC匯編語言程序設(shè)計(jì)[M]. 北京:清華大學(xué)出版社，1991.

[2] 楊季文. 80X86匯編語言程序設(shè)計(jì)教程[M]. 北京:清華大學(xué)出版社，1998.

[3] 王元珍. IBM-PC宏匯編語言程序設(shè)計(jì)[M]. 武漢:華中理工大學(xué)出版社，1990.

[4] 張昆藏. 微型計(jì)算機(jī)PC系列系統(tǒng)功能教程[M]. 北京:清華大學(xué)出版社，1992.

[5] 馮博琴，吳寧. 微型計(jì)算機(jī)原理與接口技術(shù)(第二版)[M]. 北京:清華大學(xué)出版社，2008.