汇编语言递归及应用详解[附带实例]


递归子程序(recursive subrountine)是指直接或间接调用自身的子程序。递归,调用递归子程序的做法,在处理具有重复模式的数据结构时,它是一个强大的工具。例如链表和各种类型的连接图,这些情况下,程序都需要追踪其路径。

无限递归

子程序对自身的调用是递归中最显而易见的类型。例如,下面的程序包含一个名为 Endless 的过程,它不间断地重复调用自身:
;无限递归 (Endless, asm)
INCLUDE Irvine32.inc
.data
endlessStr BYTE "This recursion never stops",0
.code
main PROC
    call Endless
    exit
main ENDP

Endless PROC
    mov edx,OFFSET endlessStr
    call WriteString
    call Endless
    ret                           ;从不执行
Endless ENDP
END main
当然,这个例子没有任何实用价值。每次过程调用自身时,它会占用 4 字节的堆栈空间让 CALL 指令将返回地址入栈。RET 指令永远不会被执行,仅当堆栈溢出时,程序终止。

递归求和

实用的递归子程序总是包含终止条件。当终止条件为真时,随着程序执行所有挂起的 RET 指令,堆栈展开。举例说明,考虑一个名为 CalcSum 的递归过程,执行整数 1 到 n 的加法,其中 n 是通过 ECX 传递的输入参数。CalcSum 用 EAX 返回和数:
;整数求和   (RecursiveSum. asm)
INCLUDE Irvine32.inc
.code
main PROC
    mov  ecx,5          ; 计数值 = 5
    mov  eax,0          ; 保存和数
    call CalcSum        ; 计算和数
L1:    call WriteDec    ; 显示 EAX
    call Crlf           ; 换行
    exit
main ENDP

;--------------------------------------------------------
CalcSum PROC
; 计算整数列表的和数
; 接收: ECX = 计数值
; 返回: EAX = 和数
;--------------------------------------------------------
    cmp  ecx,0         ; 检查计数值
    jz   L2            ; 若为零则推出
    add  eax,ecx       ; 否则,与和数相加
    dec  ecx           ; 计数值递减
    call CalcSum       ; 递归调用
L2:    ret
CalcSum ENDP
END Main
CalcSum 的开始两行检查计数值,若 ECX=0 则退出该过程,代码就跳过了后续的递归调用。当第一次执行 RET 指令时,它返回到前一次对 CalcSum 的调用,而这个调用再返回到它的前一次调用,依序前推。

下表给出了 CALL 指令压入堆栈的返回地址(用标号表示),以及与之相应的 ECX(计数值)和 EAX(和数)的值。

入栈的返回地址 ECX的值 EAX的值 入栈的返回地址 ECX的值 EAX的值
L1 5 0 L2 2 12
L2 4 5 L2 1 14
L2 3 9 L2 0 15

即使是一个简单的递归过程也会使用大量的堆栈空间。每次过程调用发生时最少占用 4 字节的堆栈空间,因为要把返回地址保存到堆栈。

计算阶乘

递归子程序经常用堆栈参数来保存临时数据。当递归调用展开时,保存在堆栈中的数据就有用了。下面要查看的例子是计算整数 n 的阶乘。阶乘算法计算 n!,其中 n 是无符号整数。第一次调用 factorial 函数时,参数 n 就是初始数字。下面给出的是用 C/C++/Java 语法编写的代码:
int function factorial(int n)
{
    if(n == 0)
        return 1;
    else
        return n * factorial(n-1);
}
假设给定任意 n,即可计算 n-1 的阶乘。这样就可以不断减少 n,直到它等于 0 为止。根据定义,0!=l。而回溯到原始表达式 n! 的过程,就会累积每次的乘积。比如计算 5! 的递归算法如下图所示,左列为算法递进过程,右列为算法回溯过程。

阶乘函数的递归调用

【示例】下面的汇编语言程序包含了过程 Factorial,递归计算阶乘。通过堆栈把 n(0〜12 之间的无符号整数 ) 传递给过程 Factorial,返回值在 EAX 中。由于 EAX 是 32 位寄存器,因此,它能容纳的最大阶乘为 12!(479 001 600 )。
; 计算阶乘 (Fact.asm)
INCLUDE Irvine32.inc
.code
main PROC
    push 5                ; 计算 5!
    call Factorial        ; 计算阶乘 (eax)
    call WriteDec         ; 显示结果
    call Crlf
    exit
main ENDP

Factorial PROC
    push ebp
    mov  ebp,esp
    mov  eax,[ebp+8]       ; 获取 n
    cmp  eax,0             ; n < 0?
    ja   L1                ; 是: 继续
    mov  eax,1             ; 否: 返回0!的值 1
    jmp  L2                ; 并返回主调程序

L1:    dec  eax
    push eax               ; Factorial(n-1)
    call Factorial

; 每次递归调用返回时
; 都要执行下面的指令

ReturnFact:
    mov  ebx,[ebp+8]       ; 获取 n
    mul  ebx               ; EDX:EAX = EAX*EBX

L2:    pop  ebp            ; 返回 EAX
    ret  4                 ; 清除堆栈
Factorial ENDP
END main
现在通过跟踪初始值 N=3 的调用过程,来更加详细地查看 Factorial。按照其说明中的记录,Factorial 用 EAX 寄存器返回结果:

push 3
call Factorial           ; EAX = 3!

Factorial 过程接收一个堆栈参数 N 为初始值,以决定计算哪个数的阶乘。主调程序的返回地址由 CALL 指令自动入栈。Factorial 的第一个操作是把 EBP 入栈,以便保存主调程序堆栈的基址指针:

Factorial PROC
    push ebp

之后,它必须把 EBP 设置为当前堆栈帧的起始地址:

mov ebp resp

现在,EBP 和 ESP 都指向栈顶,运行时堆栈的堆栈帧如下图所示。其中包含了参数 N、主调程序的返回地址和被保存的 EBP 值:


由上图可知,要从堆栈中取出 N 并加载到 EAX,代码需要把 EBP 加 8 后进行基址-偏移量寻址:

mov eax, [ebp+8]      ; 获取 n

然后,代码检查基本情况 (base case),即停止递归的条件。如果 N (EAX 当前值 ) 等于 0,函数返回 1,也就是 0! 的定义值。

cmp    eax,0        ; n>0    ?
ja    L1                 ; 是:继续
mov    eax, 1       ; 否:返回o    !的结果1
jmp    L2              ; 并返回主调程序

由于当前 EAX 的值为 3,Factorial 将递归调用自身。首先,它从 N 中减去 1,并把新值入栈。该值作为参数传递给新调用的 Factorial:

L1: dec eax
    push eax         ; Factorial(n - 1)
    call Factorial

现在,执行转向 Factorial 的第一行,计算数值为 N 的新值:

Factorial PROC
    push ebp
    mov ebp,esp

运行时堆栈又包含了第二个堆栈帧,其中 N 等于 2:


现在 N 的值为 2,将其加载到 EAX,并与 0 比较:

mov eax, [ebp+8]      ;当前 N=2
cmp    eax, 0              ; N 与 0 比较
ja    L1                        ;仍然大于0
mov    eax, 1              ;不执行
jmp    L2                    ;不执行

N 大于 0,因此,继续执行标号 L1。

大家可能已经注意到之前的 EAX,即第一次调用时分配给 Factorial 的值,被新值覆盖了。这说明了一个重要的事实:在过程进行递归调用时,应该小心注意哪些寄存器会被修改。如果需要保存这些寄存器的值,就需要在递归调用之前将其入栈,并在调用返回之后将其弹出堆栈。幸运的是,对 Factorial 过程而言,在递归调用之间保存 EAX 并不是必要的。

执行 L1 时,将会用递归过程调用来计算 N-1 的阶乘。代码将 EAX 减 1,并将结果入栈,再调用 Factorial:

L1: dec    eax            ; N = 1
    push eax              ; Factorial(1)
    call Factorial

现在,第三次进入 Factorial,堆栈中也有了三个活动的堆栈帧:


Factorial 程将 N 与 0 比较,发现 N 大于 0,则再次调用 Factorial,此时 N=0。当最后一次进入 Factorial 过程时,运行时堆栈出现了第四个堆栈帧:


在 N=0 时调用 Factorial,情况变得有趣了。下面的语句产生了到标号 L2 的分支。由于 0! =1,因此数值 1 赋给 EAX,而 EAX 必须包含 Factorial 的返回值:

mov eax,[ebp+8]         ; EAX = 0
cmp eax,0                    ; n < 0?
ja L1                             ; 是: 继续
mov eax,1                    ; 否: 返回0!的值 1
jmp L2                         ; 并返回主调程序

标号 L2 的语句如下,它使得 Factorial 返回到前一次的调用:

L2: pop ebp            ; 返回 EAX
    ret 4                    ; 清除堆栈

此时,如下图所示,最近的帧已经不在运行时堆栈中,且 EAX 的值为 1(零的阶乘)。


下面的代码行是 Factorial 调用的返回点。它们获取 N 的当前值(保存于堆栈 EBP+8 的位置),将其与 EAX(Factorial 调用的返回值)相乘。那么,EAX 中的乘积就是 Factorial 本次迭代的返回值:

ReturnFact:
    mov ebx,[ebp+8]       ; 获取 n
    mul ebx                      ; EDX:EAX = EAX*EBX

L2:    pop ebp                ; 返回 EAX
    ret 4                           ; 清除堆栈
Factorial ENDP

(EDX 中的乘积高位部分为全 0,可以忽略。)由此,上述代码行第一次得以执行,EAX 保存了表达式 1 x 1 的乘积。随着 RET 指令的执行,又一个堆栈帧从堆栈中删除:


再次执行 CALL 指令后面的语句,将 N(现在等于 2)与 EAX 的值(等于 1)相乘:

ReturnFact:
    mov ebx,[ebp+8]       ; 获取 n
    mul ebx                      ; EDX:EAX = EAX*EBX

L2:    pop ebp                ; 返回 EAX
    ret 4                          ; 清除堆栈
Factorial ENDP

EAX 中的乘积现在等于 2,RET 指令又从堆栈中移除一个堆栈帧:


现在,最后一次执行 CALL 指令后面的语句,将 N(等于 3)与 EAX 的值(等于 2)相乘:

ReturnFact:
    mov ebx,[ebp+8]       ; 获取 n
    mul ebx                      ; EDX:EAX = EAX*EBX

L2:    pop ebp                ; 返回 EAX
    ret 4                           ; 清除堆栈
Factorial ENDP

EAX 的返回值为 6,是 3! 的计算结果,也是第一次调用 Factorial 时希望进行的计算。当 RET 指令执行时,最后一个堆栈帧也从堆栈中移除。