recursion - 使用 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

这是您的函数的代码。我知道你不是在寻找答案，而是在寻找一个例子以及它是如何工作的，当你了解它是如何工作的时候，你会更容易。

.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 (跳转和链接)到函数的名称，但首先总是将返回地址存储到堆栈中: $ra所以以后如果你想回到起点你可以使用 jr $ra .如果您不保存退货地址并尝试通过 jr 访问它您很可能会收到 invalid program counter error .希望我能帮到你，祝你能更好地掌握 MIPS 编程!