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

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

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

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

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

1遞歸的本質

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

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

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

又如，數學中對自然數的定義：

(1)1是自然數；

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

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

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

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

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

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

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

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

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

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

下面我們通過剖析一個匯編語言遞歸子程序的調用和返回過程中堆棧的變化，讓學生真正掌握遞歸調用的本質。例1：以下遞歸子程序的功能是實現將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 ；遞歸調用

IP2:pop ax ；返回地址標記， 設標號IP2在代碼段的偏移為123H

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

cmp al，3ah

jb output

add al，7

output:mov dl，al

mov ah，2

int 21h

ret

disp endp ；子程序定義結束

設在主調程序中，有如下調用：

mov ax，5678h

call disp

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

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

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

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

3結論

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

參考文獻

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

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

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

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

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