汇编语言递归及应用详解[附带实例]
无限递归
子程序对自身的调用是递归中最显而易见的类型。例如,下面的程序包含一个名为 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 MainCalcSum 的开始两行检查计数值,若 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 PROC
push 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 ; 并返回主调程序
L1: dec eax
push eax ; Factorial(n - 1)
call Factorial
Factorial PROC
push ebp
mov ebp,esp
现在 N 的值为 2,将其加载到 EAX,并与 0 比较:
mov eax, [ebp+8] ;当前 N=2
cmp eax, 0 ; N 与 0 比较
ja L1 ;仍然大于0
mov eax, 1 ;不执行
jmp L2 ;不执行
大家可能已经注意到之前的 EAX,即第一次调用时分配给 Factorial 的值,被新值覆盖了。这说明了一个重要的事实:在过程进行递归调用时,应该小心注意哪些寄存器会被修改。如果需要保存这些寄存器的值,就需要在递归调用之前将其入栈,并在调用返回之后将其弹出堆栈。幸运的是,对 Factorial 过程而言,在递归调用之间保存 EAX 并不是必要的。
执行 L1 时,将会用递归过程调用来计算 N-1 的阶乘。代码将 EAX 减 1,并将结果入栈,再调用 Factorial:
L1: dec eax ; N = 1
push eax ; Factorial(1)
call 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: pop ebp ; 返回 EAX
ret 4 ; 清除堆栈
下面的代码行是 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
再次执行 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
现在,最后一次执行 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
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频