MIPS 帮助：递归函数

Question

我正在尝试将此递归函数编码为 MIPS。我的问题是我不确定如何执行递归步骤。
我很确定我做对了其余部分。

int recur(int n) {
    if(n == 1 || n == 2) {
           return 2;
    } else {
           return (n-4)+n*recur(n-2);
    }
}

.data

promptMessage: .asciiz "Enter a number that is greater than or equal to 0: "
resultMessage: .asciiz "\nThe answer is: "
input: .word 0
answer: .word 0

.text
.globl main

main:
#Read the number from the user
li $v0, 4           
la $a0, promptMessage       
syscall

li $v0, 5           
syscall         

sw $v0, input           

#Call the function
lw $a0, input           
jal recur           
sw $v0, answer      

#Display result
li $v0, 4
la $a0, resultMessage       
syscall

li $v0, 1           
lw $a0, answer          
syscall

.globl recur

recur:
addi $sp, $sp, -8       
sw $a0, 0($sp)          
sw $ra, 4($sp)          

#Base Case  if(n == 0 || n == 1) return 2;
li $v0, 2
beq $a0, $zero, DONE
beq $a0, 1, DONE

#RECURSIVE STEP
addi $a0, $a0, -2       
jal recur

Answer 1

你做得很好。首先创建 C 代码。你们很亲密。

我不得不添加计算步骤和函数结尾代码。

此外，还有一个错误，在 main 打印数字后，有 no 系统调用 10（退出），因此代码会失败并无限递归。

我稍微修改了 C 代码，使其与 MIPS 代码更兼容。

为了好玩和便于测试，我将 main 更改为循环并重新提示，直到它得到一个负数。

我已经清理并测试了代码，添加了注释[请原谅不必要的样式清理]：

    .data

# NOTE: these should appear first to maintain alignment to a 4 byte boundary
# (or the .align 4 will do it) otherwise, the lw/sw ops can fail on an
# alignment exception
    .align  4
input:      .word       0
answer:     .word       0

promptMessage:  .asciiz "Enter a number that is greater than or equal to 0 (-1 to stop): "
resultMessage:  .asciiz "\nThe answer is: "
nl:         .asciiz "\n"

    .text   .globl

main:
    # prompt user
    li      $v0,4
    la      $a0,promptMessage
    syscall

    # Read the number from the user
    li      $v0,5
    syscall
    sw      $v0,input

    # negative value means stop
    # NOTE: added this
    bltz    $v0,main_exit

    # Call the function
    lw      $a0,input
    jal     recur
    sw      $v0,answer

    # Display result message
    li      $v0,4
    la      $a0,resultMessage
    syscall

    # display number
    li      $v0,1
    lw      $a0,answer
    syscall

    # output newline
    li      $v0,4
    la      $a0,nl
    syscall

    # NOTE: this was added to allow multiple tries, but without it, there was
    # the bug below
    j       main

    # BUG: syscall to exit here was _missing_ so got fallthrough into "recur"
    # causing the stack to overflow
main_exit:
    li      $v0,10
    syscall

    .globl  recur

# recur -- recursion
#
# arguments:
#   a0 -- the "n" value
#
# pseudo code:
# * int
# * recur(int n)
# * {
# *     int r;
# *
# *     if (n == 1 || n == 2) {
# *         return 2;
# *     }
# *
# *     r = recur(n - 2);
# *
# *     return (n - 4) + (n * r);
# * }
recur:
    addi    $sp,$sp,-8
    sw      $a0,0($sp)
    sw      $ra,4($sp)

    # Base Case  if(n == 0 || n == 1) return 2;
    li      $v0,2
    beq     $a0,$zero,recur_done
    beq     $a0,1,recur_done

    # RECURSIVE STEP
    addi    $a0,$a0,-2          # n -= 2
    jal     recur
    lw      $a0,0($sp)          # we need "n" back (not (n - 2))

    # NOTE: this calculation was missing
    mul     $v0,$v0,$a0         # r *= n (i.e. (n * r))
    addi    $a0,$a0,-4          # n -= 4 (i.e. (n - 4))
    add     $v0,$v0,$a0         # sum them

    # NOTE: this is the standard reversal for this function's stack prolog
recur_done:
    lw      $a0,0($sp)
    lw      $ra,4($sp)
    addi    $sp,$sp,8
    jr      $ra

MIPS 帮助：递归函数

MIPS Help: Recursive Functions

assembly

mips

mars-simulator

qtspim