汇编语言学习系列递归实现

浏览数：24 / 时间：2015年06月08日

假如汇编语言要实现如下C语言的功能，编译环境Ubuntu14.04（32位）。

#include<stdio.h>
int refact(int n){
    if(n == 1)
        return 1;
    else
        return n * refact(n - 1);
}

int main(){
    int a = 4;
    printf("%d\n", refact(a));
    return 0;
}

无论对于递归实现还是循环实现，汇编都是将转换为跳转语句实现。可以把上面的代码转换为

refact:
    if((n-1) <= 0)
    goto done;

    body-statement
        
done:

汇编代码refact.s

.section .data
        a: .int 4
        format: .asciz "%d\n"
.section .text
.global _start
_start:
        pushl %ebp
        movl %esp, %ebp
        subl $8, %esp #allocate storage space
        
        movl a, %edx    #get a
        movl %edx, (%esp)    #save value of a on stack
        
        call refact
        
        pushl %eax
        pushl $format
        call printf
        movl $0, (%esp)
        call exit                    
        
refact:
        pushl %ebp
        movl %esp, %ebp
        pushl %ebx
        subl $4, %esp    #allocate storage space
        
        movl 8(%ebp), %ebx    #get n
        cmpl $1, %ebx    
        jle done    #test (n-1) >= 0
        
        leal -1(%ebx), %eax    #(n-1)
        movl %eax, (%esp)　　#save (n-1) on the stack
        call refact
        imul %ebx, %eax　　#use %eax to save result 
        
done:    
        addl $4, %esp    #release space
        popl %ebx
        popl %ebp
        ret