MIPS 中的递归

Question

我想在 MIPS 的汇编中实现一个递归程序。更具体地说，我想实现著名的斐波那契函数。

下面是 C 中的实现：

int fib(int n) {
    if(n<2)
        return 1;
    return fib(n-1)+fib(n-2);
}

Answer 1

以下是在 MIPS 汇编中执行递归阶乘函数的代码。将其更改为斐波那契数列作为练习留给读者。 （注意：此代码中未优化延迟槽，因为它是为了可读性而设计的。）

# int fact(int n)
fact:
    subu    sp, sp, 32  # Allocate a 32-byte stack frame
    sw  ra, 20(sp)  # Save Return Address
    sw  fp, 16(sp)  # Save old frame pointer
    addiu   fp, sp, 28  # Setup new frame pointer
    sw  a0,  0(fp)  # Save argument (n) to stack

    lw  v0, 0(fp)   # Load n into v0
    bgtz    v0, L2      # if n > 0 jump to rest of the function
    li  v0, 1       # n==1, return 1
    j   L1      # jump to frame clean-up code

L2:
    lw  v1, 0(fp)   # Load n into v1
    subu    v0, v1, 1   # Compute n-1
    move    a0, v0      # Move n-1 into first argument
    jal fact        # Recursive call

    lw  v1, 0(fp)   # Load n into v1
    mul v0, v0, v1  # Compute fact(n-1) * n

    #Result is in v0, so clean up the stack and return
L1:
    lw  ra, 20(sp)  # Restore return address
    lw  fp, 16(sp)  # Restore frame pointer
    addiu   sp, sp, 32  # Pop stack
    jr  ra      # return
    .end    fact

Answer 2

-将n-1加载到$a0中

-使用jal指令递归调用fib。

-从$v0寄存器中获取结果。

-将n-2加载到$a0中

-使用jal指令递归调用fib。

-从$v0寄存器中获取结果。

然后，有一些与addu指令有关的东西......

哦，是的，您必须使用分支检查if，但这与递归无关。

如果您需要帮助，编译器是您的朋友。

$gcc -c -g fib.c

$objdump -S fib.o

但

$gcc -S -mrnames fib.c -o fib.s

会更清晰。

Answer 3

提示 - 考虑一个堆栈。

顺便说一句，就复杂性（时间和空间）而言，递归对于解决问题来说确实是一个糟糕的解决方案。一个循环和两个变量会工作得更好。

Answer 4

将 C 函数编译为目标文件，然后查看

objdump -d fib.o

“可能”是您的起点。