递归在MIPS [英] Recursion in MIPS

问题描述

我想要实现组装递归程序MIPS。更具体地说，我要实现众所周知的斐波那契功能。

下面是用C实现：

  INT FIB（INT N）{
    如果（正2）
        返回1;
    返回FIB（N-1）+ FIB（N-2）;
}
 

解决方案

下面是code做在MIPS汇编递归阶乘函数。改变它做的斐波那契数是作为练习留给读者。 （注：延迟槽未在此code优化，因为它是专为阅读）

 ＃INT事实（INT N）
事实：
    苏布SP，SP，32＃分配一个32字节堆栈帧
    SW RA，20（SP）＃保存返回地址
    SW FP，16（SP）＃保存老帧指针
    ADDIU FP，SP，28＃设置新的帧指针
    SW A0，0（FP）＃保存参数（n）的堆栈    LW V0，0（FP）＃负载N为V0
    bgtz V0，L2＃如果n＆GT; 0跳转到函数的其余部分
    李V0，1＃N == 1，返回1
    ĴL1＃跳转到帧清理codeL2：
    LW V1，0（FP）＃负载N为V1
    苏布V0，V1，1＃计算n-1个
    此举A0，V0＃移动n-1个到第一个参数
    日航实际上＃递归调用    LW V1，0（FP）＃负载N为V1
    MUL V0，V0，V1＃计算事实（N-1）* N    #Result是V0，所以清理堆栈和返回
L1：
    LW RA，20（SP）＃恢复返回地址
    LW FP，16（SP）＃恢复帧指针
    ADDIU SP，SP，32＃流行栈
    JR RA＃回报
    事实上.END
 

I want to implement a recursive program in assembly for MIPS. More specifically, I want to implement the well-known Fibonacci function.

Here's the implementation in C:

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

解决方案

Here is the code to do a recursive factorial function in MIPS assembly. Changing it to do Fibonacci is left as an exercise to the reader. (Note: delay slots aren't optimized in this code, as it's designed for readability.)

# 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

这篇关于递归在MIPS的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！