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

递归子程序（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（和数）的值。 

即使是一个简单的递归过程也会使用大量的堆栈空间。每次过程调用发生时最少占用 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 寄存器返回结果：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

再次执行 CALL 指令后面的语句，将 N（现在等于 2）与 EAX 的值（等于 1）相乘：

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

现在，最后一次执行 CALL 指令后面的语句，将 N（等于 3）与 EAX 的值（等于 2）相乘：

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