另一个递归调用的实例

带指针的阶乘

Recursive Procedure / 递归程序

void s_helper(int x, int *accum)
{
    if (x <= 1)
        return;
    else{
        int z = *accum * x;
        s_helper(x - 1, accum);
    }
}

Top-Level Call

int sfact(int x)
{
    int val = 1;
    s_helper(x, &val);
    return val;
}

这个阶乘和刚才那个不一样, 刚才那个实际上是利用通用寄存器 eax, 它既作为返回值又作为运算的某一个变量.

这个代码也是一个阶乘, 但是它多了一个条件, 就是我希望你把这个结果的值存放在某一个地址里面, 针对这个代码就是存到临时变量 val 里面. 这样我强制要求你运算过程中要带一个指针.

创建指针

_sfact:
    pushl %ebp  ; Save ebp
    movl %esp, %ebp ; Set ebp
    subl $16, %esp  ; add 16 bytes 栈顶上分配 16 字节空间给你
    movl 8(%ebp), %edx  ; edx = x
    movl $1, -4(%ebp)   ; val = 1

首先 int val = 1, 这个 val 是一个局部变量. 我们之前说过编译器倾向于把局部变量放到寄存器里面, 因为访问寄存器比访问内存要快, 但是这里并没有把 val 放到寄存器里面, 而是放到了栈中, 因为这里对 val 做了一个取地址的操作, 所以编译器只能把它放在栈帧里面.

然后是设置栈帧

val 地址为 ebp - 4

传递指针

调用 s_helper 过程

    leal -4(%ebp), %eax ; Compute &val
    pushl %eax  ; push on stack
    pushl %edx  ; push x
    call s_helper   ; call
    movl -4(&ebp), %eax ; return val
    ......  ; Finish

因为最后的结果要放在 val 里面, 所以要首先把它的地址计算出来. 这就用到 leal 指令了, (leal 本分工作是计算地址值, 第二个是也可以参与一些数值的运算), 这里 leal 是计算地址

然后 pushl %eax, 就是参数压栈, 从右往左压, 把 val 的地址压栈了. 接下来就是传 x 参数了.

使用指针

void s_helper(int x, int *accum)
{
    ...
    int z = *accum * x;
    *accum = z;
    ...
}

...
    movl %ecx, %eax ; z = x
    imull (%edx), %eax  ; z *= *accum
    movl %eax, (%edx)   ; *accum = z
...

%ecx 存储变量 x, %edx 存储变量 accum 这个指针的地址

这里我们把它建立栈帧的过程, 以及传递参数的过程省略掉