使用 MIPS 汇编的递归函数

Question

我在作业中遇到了一些问题，希望得到一些帮助。我不是要答案，我更喜欢把两个和两个放在一起自己弄清楚，但是我对 MIPS 知之甚少，所以我很难知道从哪里开始。

这是我的开头

.data


.text
main:

addi $sp, $sp, -16  #prepare stack for 4 items
sw $s0, 0($sp)
sw $s1, 4($sp)
sw $s2, 8($sp)
sw $ra, 12($sp)
move $s0, $a0
move $s1, $a1

add $s2, $s0, $s1   #add two previous numbers and store result in $s2

move $v0, $s2   #put answer into $v0

lw $s0, 0($sp)
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
jr$ra

本质上，我们将使用一个递归函数来计算斐波那契数列，并使用一个循环来打印出斐波那契数列的前 10 个数。

我查了很多例子，但它们都使用了我们还没有学过的指令，所以我无法理解它，我只能假设我们不希望使用它们。在上面的代码中，我实际上是在创建一个堆栈来存储 $ra 以及三个值，即要相加的两个数字和总和。我的部分问题是了解函数的开始和结束位置以及正在完成的工作的全部内容。

我们还得知要打印您使用以下内容

li $v0, 1
move $a0, $s0
syscall

我认为这是打印存储在 $v0 中的值是否正确？

Answer 1

这里有一些提示：

你要写一个递归函数，但你根本就不是在写一个函数。要在 MIPS assembler 中编写此函数，我建议您首先使用高级语言 (C) 编写它。所以它会像这样：

int fib(int n)
{
  if(n == 0 or n == 1)
    return n;
  else return fib(n-1) + fib(n-2);
}

第一行检查您是否处于递归的基本情况下（n=0 或 n=1）。如果是这样的话，fib(n) returns n。否则，递归步骤将 returns fib(n-1) 加上 fib(n-2) 的总和。

因此您必须编写一个函数，定义 input/output 参数（哪个寄存器将保存 n，哪个寄存器将 return fib(n)。手动编译C代码。要启动一个功能，只需添加一个标签

fib:

然后将您的堆栈管理代码放在那里。
然后将 IF-THEN-ELSE 转换为 MIPS assemble。
要发出递归调用，请使用 jal 指令。
在使用 jr $ra 从函数中 return 之前从堆栈中恢复保存的值。
您的主程序将加载输入参数（用于输入参数的寄存器n），然后jal fib。

Answer 2

这是您的函数的代码。我知道您不是在寻找答案，但有时寻找示例并查看其工作原理可以让您更轻松地了解它的实际工作原理。

.data
msg1: .asciiz "Give a number: "

.text
.globl main
main:
    li $v0,  4
    la $a0,  msg1
    syscall             # print msg
    li $v0,  5
    syscall             # read an int
    add $a0, $v0, $zero # move to $a0

    jal fib             # call fib

    add $a0, $v0, $zero
    li  $v0, 1
    syscall

    li $v0, 10
    syscall

fib:
    # $a0 = y
    # if (y == 0) return 0;
    # if (y == 1) return 1;
    # return fib(y - 1) + fib(y - 2);

    #save in stack
    addi $sp, $sp, -12 
    sw   $ra, 0($sp)
    sw   $s0, 4($sp)
    sw   $s1, 8($sp)

    add $s0, $a0, $zero

    addi $t1, $zero, 1
    beq  $s0, $zero, return0
    beq  $s0, $t1,   return1

    addi $a0, $s0, -1

    jal fib

    add $s1, $zero, $v0         # $s1 = fib(y - 1)

    addi $a0, $s0, -2

    jal fib                     # $v0 = fib(n - 2)

    add $v0, $v0, $s1           # $v0 = fib(n - 2) + $s1

    exitfib:

        lw   $ra, 0($sp)        # read registers from stack
        lw   $s0, 4($sp)
        lw   $s1, 8($sp)
        addi $sp, $sp, 12       # bring back stack pointer
        jr $ra

    return1:
        li $v0,1
        j exitfib

    return0:     
        li $v0,0
        j exitfib

正如 Gusbro 所说，为了在 mips 中使用递归，您必须做两件事。 jal（跳转和 link）到函数名，但首先始终将 return 地址存储到堆栈中，$ra，所以将来如果你想 return回到开头就可以使用jr $ra了。如果您不保存 return 地址并尝试通过 jr 访问它，您很可能会得到一个 invalid program counter error.

Answer 3

这解释了如何在 MIPS 中实现 Fibonacci 函数以及如何将 MIPS 函数转换回等效的 C 代码，非常详细：Fibonacci function in MIPS by illinois.edu

基本案例的代码：

fib:
bgt $a0, 1, recurse
move $v0, $a0
jr $ra

转换基本案例的代码。

fib:
bgt $a0, 1, recurse
move $v0, $a0
jr $ra

在堆栈上保存被调用者和调用者保存的寄存器。递归：

sub $sp, $sp, 12 # We need to store 3 registers to stack 
sw $ra, 0($sp) # $ra is the first register 
sw $a0, 4($sp) # $a0 is the second register, we cannot assume $a registers will not be overwritten by callee

递归调用 fib:

addi $a0, $a0, -1 # N-1 
jal fib 
sw $v0, 8($sp) # store $v0, the third register to be stored on the stack so it doesn’t get overwritten by callee

再次递归调用 fib:

  lw $a0, 4($sp) # retrieve original value of N  
  addi $a0, $a0, -2 #N-2  jal fib

Answer 4

用 C 或 C++ 编写 add() 的递归版本，然后使用此程序开发 MIPS 获取两个整数 0< ≤255 和 0< ≤255 以及 returns 作为输入的程序 $v1.

中 add(,) 的结果

使用 MIPS 汇编的递归函数

Recursive function using MIPS assembly

recursion

mips

fibonacci