基于匯編語言的遞歸算法教學設計探討

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

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

中圖分類號：G642文獻標識碼：B

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

1遞歸的本質(zhì)

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

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

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

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

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

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

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

① 遞歸的形式；②遞歸的結束條件。

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

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

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

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

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

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

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

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

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 ；返回地址標記， 設標號IP2在代碼段的偏移為123H

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

cmp al，3ah

jb output

add al，7

output:mov dl，al

mov ah，2

int 21h

ret

disp endp ；子程序定義結束

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

mov ax，5678h

call disp

IP1:…… ；設標號IP1在代碼段的偏移為200H

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

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

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

3結論

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

參考文獻

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

[2] 楊季文. 80X86匯編語言程序設計教程[M]. 北京:清華大學出版社，1998.

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

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

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