用汇编与c解决递归问题之比较
owlbird
事先声明不是有意刺激大家,绝没有打击大家学习汇编语言的高涨热情,只是由于用汇编写这个程序有许多感触,觉得用汇编来解决数学问题特别是递归问题是一件多么痛苦的事,看来汇编的优势还是在于系统
递归求解f(n)=f(n-1)+f(n-2),f(1)=1,f(2)=1
如果用汇编来写,必须画一个草图来分析子程序调用时堆栈的情况,也就是说你必须首先有一个回推的过程,以n=3来举例(注:分割符之间表示一帧)
bp
1
ip
1
---------
bp
2 ;入栈时
ip
2
---------
bp
3
ip
3
bp
1 [bp-14]
ip
1
--------
bp
1 [bp-6]
ip ;出栈时
2
--------
bp
2 ------> [bp-6]+[bp-14]
ip
3
以下是汇编源程序
messem macro mess ;宏定义
mov ah,09
lea dx,mess
int 21h
endm
data segment
swapper dw 0 ;用来做标尺
message db 'please input the number ','$'
messerr db 'please input the number between 0~9','$'
crlf db 13,10,'$'
decdec dw 10d
data ends
stack_seg segment
dw 128 dup(0)
tos label word
stack_seg ends
code segment
main proc far
assume cs:code,ds:data,ss:stack_seg
start:
mov ax,stack_seg
mov ss,ax
mov sp,offset tos
push ds
sub ax,ax
push ax
mov ax,data
mov ds,ax
mov es,ax
mov bx,0
messem message ;调用宏定义
messem crlf ;调用宏定义
input:
mov ah,01
int 21h
cmp al,13
jz result1
cmp al,'0'
jb error
cmp al,'9'
ja error
result:
mov ah,0
sub al,30h
xchg ax,bx
mul [decdec]
add bx,ax
jmp input
error:
messem messerr;调用宏定义
messem crlf ;调用宏定义
mov bx,0
jmp input
result1:
messem crlf ;调用宏定义
mov ax,bx
push bx
call fact
pop bx
mov di,ax ;ax用来保存结果
messem messres ;调用宏定义
call disdec
ret ;返回dos
main endp
fact proc near ;递归子程序
push ax
push bp
mov bp,sp
mov ax,[bp+6]
cmp ax,2
je done
cmp ax,1
je exit
fact1:
dec ax
push ax
call fact ;此递归程序注意必须有两次递归递用
pop ax
mov ax,[bp-6] ;将前两项相加
add ax,[bp-14]
mov [bp+2],ax
jmp exit
done:
mov ax,1
mov [bp+2],ax
push ax
call fact ;此递归程序注意必须有两次递归递用
pop ax
exit:
pop bp
pop ax
ret
fact endp
disdec proc near ;将16进制转化为10进制的子程序
mov ax,di
mov cx,10000d
call divdec
mov cx,1000d
call divdec
mov cx,100d
call divdec
mov cx,10d
call divdec
mov cx,1d
call divdec
mov bx,0
mov swapper,bx
ret
disdec endp
divdec proc near
mov dx,0
div cx
push dx
cmp al,0
jz cmpswp
jmp disok
cmpswp:
mov bx,[swapper]
cmp bx,0
jz exit1
disok:
add al,30h
mov dl,al
mov ah,02
int 21h
mov bx,1
mov [swapper],bx
exit1:
pop dx
mov ax,dx
ret
divdec endp
code ends
end start
以下是c++源程序,简直太方便了,因为c++通过函数来完成了递归调用(即入栈出栈的过程)
#include <iostream.h>
#include <iomanip.h>
int fib(int n);
void main()
{
int m;
cout <<"please input number"<<endl;
cin >>m;
if(m<=0)
cout <<"please input m>0"<<endl;
else
cout <<fib(m)<<endl;
}
int fib(int n)
{
int result;
if(n==2 || n==1)
result=1;
else
result=fib(n-1)+fib(n-2);
return result;
}
希望大家学习汇编语言之前,最好有一门高级语言作为基础.
