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

递归子程序（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 指令执行时，最后一个堆栈帧也从堆栈中移除。