MIPS 中的递归函数调用（带堆栈）

Question

有人可以解释存储在堆栈中并加载回来的递归函数调用吗？真的很混乱。

预先感谢。

例如，我试图理解从 C 到 MIPS 的阶乘函数（递归）。但我不能。

Answer 1

尽量不要担心递归。

阶乘函数看起来像这样：

int fact ( int n ) {
    if ( n <= 1 ) return 1;
    return fact ( n-1 ) * n;   // or, return n * fact ( n-1 );
}

MIPS 翻译为：

fact:
    ble $a0, 1, EndIf1
    addiu $sp, $sp, -8       # allocate 8 bytes of stack space
    sw $a0, 4($sp)           # store n into the stack for later use in multiplication
    sw $ra, 0($sp)           # store return address for later use by return
    addi $a0, $a0, -1        # compute n-1 and pass to fact as parameter
    jal fact                 # fact function result (return value) is in $v0
    lw $a0, 4($sp)           # restore n from stack location, previously saved
    mul $v0, $v0, $a0        # perform multiplication sending result to $v0
    lw $ra, 0($sp)           # load return address
    addiu $sp, $sp, 8        # deallocate the 8 bytes previously allocated
    jr $ra                   # return to caller
EndIf1:
    li $v0, 1
    jr $ra        

重要的是要认识到，在汇编语言中，返回地址是机器代码值，它指的是调用者调用站点之前的指令位置，该位置应在函数完成时恢复。返回地址隐藏在 C 代码和其他高级语言中，而它必然暴露在机器代码/汇编语言中。

jr $ra

指令通过使用返回地址将控制权转移回调用者（同时返回值在

$v0

寄存器中与调用者共享）。

jal

指令自动设置

$ra

寄存器，可以将其视为函数的附加参数（完成时返回的位置）。由于

jal

重新利用/覆盖

$ra

，如果其中有一个重要的值（有），则必须将其移至在函数调用后仍保留的其他位置，以便稍后在返回时使用。

对于

$a0

也是如此——我们需要将

n-1

放入

$a0

中才能调用

fact

，但是，在调用fact之后我们需要

n

，所以也保存

 n

（来自

$a0

）入栈并在调用后恢复。

---

好的，这是一个非递归版本（依赖于上面的

fact

）：

int non_recursive_fact ( int n ) {
    if ( n <= 1 ) return 1;
    return fact ( n-1 ) * n;   // or, return n * fact ( n-1 );
}
    

及其汇编代码：

non_recursive_fact:
    ble $a0, 1, EndIf1
    addiu $sp, $sp, -8
    sw $a0, 4($sp)
    sw $ra, 0($sp)
    addi $a0, $a0, -1
    jal fact
    lw $a0, 4($sp)
    mul $v0, $v0, $a0
    lw $ra, 0($sp)
    addiu $sp, $sp, 8
    jr $ra
EndIf1:
    li $v0, 1
    jr $ra        

因此，您会看到每个函数的代码都可以相同，即使前者是递归的而后者不是。