我将如何在 QtSpim/MIPS 中编写下面的递归序列

Question

我正在尝试在 MIPS/QtSpim 中编写以下序列：

a(n) = a(n-1) + 2a(n-2)

其中 a(0) = a(1) = 1

代码应提示用户输入 n 的值并显示 结果在控制台中。我需要对嵌套使用递归 程序链接以实现代码。

我试过下面的代码，但是如果我输入 n 大于 2，我会一直出错：

.data
a0: .word 1
a1: .word 1
n: .word 0
an: .word 0

.text
.globl main

main:
    # Prompt user to enter the value of n
    li $v0, 4
    la $a0, prompt
    syscall

    # Read the value of n from the user
    li $v0, 5
    syscall
    move $s0, $v0

    # Call the sequence function
    move $a0, $s0
    jal sequence

    # Display the result
    li $v0, 1
    lw $a0, an
    syscall

    # Exit program
    li $v0, 10
    syscall

sequence:
    addi $sp, $sp, -4
    sw $ra, 0($sp)
    beq $a0, 0, a0_case
    beq $a0, 1, a1_case
    addi $a0, $a0, -1
    jal sequence
    lw $t0, an
    addi $a0, $a0, -1
    jal sequence
    lw $t1, an
    add $v0, $t0, $t1
    sll $t1, $t1, 1
    add $t0, $t0, $t1
    sw $t0, an
    j end

a0_case:
    li $v0, 1
    sw $v0, an
    j end

a1_case:
    li $v0, 1
    sw $v0, an

end:
    lw $ra, 0($sp)
    addi $sp, $sp, 4
    jr $ra

.data
prompt: .asciiz "Enter the value of n: "

.text

Answer 1

该代码不遵循调用约定。您是想使用标准调用约定还是自己编写？

在任何情况下，寄存器都混淆了，递归调用破坏了属于递归调用者的值。不用说，CPU 寄存器一次只能保存一个值，因此，如果/当重新用于保存不同的变量时，那么前一个变量的值就会丢失。

• $a0

  不是离开

  n

  的安全位置，任何给定递归调用的参数，因为每个递归调用都会修改该寄存器。在第一次递归调用之后需要参数才能进行第二次这样的调用，但它已被第一次递归调用删除。

• $t0

  也不是临时数据的安全位置，因为它无法在第二次递归调用后存活下来，因为从广义上讲，该函数还修改了

  $t0

  :

    jal sequence
    lw $t0, an        # t0, assigned here, will be wiped out by the next jal
                      # if the recursion is deep enough
    addi $a0, $a0, -1
    jal sequence
    lw $t1, an
    add $v0, $t0, $t1 # but this code expects it to have a meaningful value 
                      # e.g. as per the above assignment!
                      # but it doesn't since the recursive call 
                      # also used $t0 for its own purposes.

• 使用全局变量，

  an: .word 0

  存储递归函数的返回值是非标准的并且也容易出错（尽管在这种特殊情况下可能有效）。返回值应该只在

  $v0

  中返回。从广义上讲，全局变量不是线程安全的，不可重入的，也不是递归友好的，所以根据调用约定使用 CPU 寄存器和调用堆栈而不是全局变量。

• 下面的代码序列设置了

  $v0

  和

  an

  但是不同的值。我没有看到

  $v0

  在任何地方使用，所以

  add

  指令没有意义。

     lw $t1, an
     add $v0, $t0, $t1
     sll $t1, $t1, 1
     add $t0, $t0, $t1
     sw $t0, an
     j end

---

因此，您需要做的是：(a) 提供并使用存储，该存储将在

n

最初的

$a0

函数调用中幸存下来，并且还用于第一次递归调用的临时结果（注意：已经

$ra

）。 (b) 删除

an

全局变量并使用

$v0

专门用于返回值，以及 (c) 修复拼写错误。