一个递归调用的实例

int rfact(int x)
{
    int rval;
    if(x <= 1)
        return 1;
    rval = rfact(x - 1);
    return rval * x;
}

这个例子比较简单, 做了一个阶乘, 给你一个 x 算出 x 的阶乘

寄存器的使用情况实际上直接告诉你了, %eax 直接参与运算, 而它同时又是返回值, 就是子过程的返回值直接和父过程当前的 x 进行计算, 又用作向上一层的返回值.

%ebx 使用前保存旧值, 退出前恢复

.globl rfact
    .type   rfact, @function
rfact:
    pushl %ebp
    movl %esp, %ebp
    pushl %ebx

    movl 8(%ebp), %ebx
    cmpl $1. %ebx
    jle .L78
    leal -1(%ebx), %eax
    pushl %eax
    call rfact
    imull %ebx, %eax
    jmp .L79
    .align 4
.L78:
    movl $1, %eax
.L79:
    movl -4(%ebp), %ebx
    movl %ebp, %esp
    popl %ebp
    ret

栈帧的建立 (分配) 过程

首先我们看方框内的代码

第一条指令, 说过了, 就是把原来 ebp 的值保留在栈里面. 每个过程默认都使用 ebp 作为基址, 所以每一次过程调用, ebp 的值就会改变.

第二个就是相当于建立了新的 ebp, 新的 ebp 指向了旧的 ebp 的值, 就是栈帧的基址在这里.

第三个, ebx 是作为被调用者负责保存恢复的寄存器, 你要把它存到栈帧当中

递归体分析

movl 8(%ebp), %ebx  ; ebx = x
    cmpl $1. %ebx   ; compare x : 1

; 递归体
    jle .L78    ; if <= goto Term
    leal -1(%ebx), %eax ; eax = x - 1
    pushl %eax  ; push x - 1
    call rfact  ; rfact(x - 1)
    imull %ebx, %eax    ; rval * x

    jmp .L79    ; goto done

.L78:   ; Term :
    movl $1, %eax   ; return val = 1
.L79:   ; done

为了简化分析, 这里将寄存器的使用告诉大家, %ebx 存储 x 的值, ebp 本身指向 old ebp, ebp + 4 指向函数的返回地址, ebp + 8 就相当于输入参数, 这里面参数 x 是唯一的输入参数.

%eax 临时存储 x - 1; 过程实例 rfact(x - 1) 的返回值; 本过程的返回值