recursion - 卡在 MIPS 递归函数上

Question

我正在 MIPS 中做作业，我觉得我的逻辑是合理的，但我无法让代码产生正确的输出。任何人都可以查看我所拥有的并提供帮助吗？这是我正在尝试实现的 C 中的相应函数。

int function1(int n) {
if (n <= 3) {
    int ans1 = (3*n)-5;
    return ans1;
  }
else {
    int ans1 = (n-1)*function1(n-1) + function1(n-2) - n;
    return ans1;
  }
}

这就是我在 MIPS 中所拥有的。对于示例输出，当用户输入 8 时，输出应该是 1096。我得到 22,735，所以显然我搞砸了。

.data

message1: .asciiz "Enter an integer\n"
message2: .asciiz "The integer is: "

.text
.globl main

main:

la $a0, message1
li $v0, 4
syscall # print message1 string

li $v0, 5
syscall # get user input 

move $a0, $v0 # int n 
jal function # call function                  
move $s0, $v0 # save function return value

la $a0, message2
li $v0, 4
syscall # print message2 string

move $a0, $s0
li $v0, 1
syscall # print the solution computed by the recursive function

li $v0, 10
syscall # exit 

function:

addi $sp, $sp, -12 # allocate memory on stack
sw $ra, 0($sp) # save return address
sw $a0, 4($sp) # save argument

ble $a0, 3, base_case # if n is <= 3 go to base case

addi $a0, $a0, -1 # n -= 1
jal function # recursive call
lw $a0, 4($sp) # load n

mul $v0, $v0, $a0 # (n-1) * function(n-1)
sw $v0, 8($sp) # save result

lw $a0, 4($sp) # load n
addi $a0, $a0, -2 # set n -= 2
jal function # recursive call

lw $t0, 8($sp) # load (n-1) * function(n-1)
add $v0, $v0, $t0 # add f(n-2) and (n-1) * f(n-1)

lw $t1, 4($sp) # load n 
sub $v0, $v0, $t1 # (n-1) * f(n-1) + f(n-2) - n

lw $ra, 0($sp) # load return address
addi $sp, $sp, 12 # free stack
jr $ra # return

base_case:

li $t5, 3
mul $v0, $a0, $t5 # (n*3) 
addi $v0, $v0, -5 # (n*3) - 5

lw $ra, 0($sp) # load return address
addi $sp, $sp, 12 # free stack
jr $ra # return

标签： recursionassemblymips

Answer 1

当用户输入 8 时，输出应该是 1096。

在考虑您的 MIPS 代码之前，您的C代码似乎也没有产生正确的结果：

#include <stdio.h>

int function1(int n) {
    if (n <= 3) {
        return 3 * n - 5;
    }

    return (n - 1) * function1(n - 1) + function1(n - 2) - n;
}

int main() {
    printf("%d\n", function1(8));

    return 0;
}

此代码打印 7842，而不是您声明的 1096。也许这就是我们应该开始调试的地方。

手动仔细检查：

function1(8)
7 * function1(7) + function1(6) - 8
7 * (6 * function1(6) + function1(5) - 7) + (5 * function1(5) + function1(4) - 6) - 8
7 * (6 * (5 * function1(5) + function1(4) - 6) + (4 * function1(4) + function1(3) - 5) - 7) + (5 * (4 * function1(4) + function1(3) - 5) + (3 * function1(3) + function1(2) - 4) - 6) - 8
7 * (6 * (5 * (4 * function1(4) + function1(3) - 5) + (3 * function1(3) + function1(2) - 4) - 6) + (4 * (3 * function1(3) + function1(2) - 4) + 4 - 5) - 7) + (5 * (4 * (3 * function1(3) + function1(2) - 4) + 4 - 5) + (3 * 4 + 1 - 4) - 6) - 8
7 * (6 * (5 * (4 * (3 * function1(3) + function1(2) - 4) + 4 - 5) + (3 * 4 + 1 - 4) - 6) + (4 * (3 * 4 + 1 - 4) + 4 - 5) - 7) + (5 * (4 * (3 * 4 + 1 - 4) + 4 - 5) + (3 * 4 + 1 - 4) - 6) - 8
7 * (6 * (5 * (4 * (3 * 4 + 1 - 4) + 4 - 5) + (3 * 4 + 1 - 4) - 6) + (4 * (3 * 4 + 1 - 4) + 4 - 5) - 7) + (5 * (4 * (3 * 4 + 1 - 4) + 4 - 5) + (3 * 4 + 1 - 4) - 6) - 8

> python3
Python 3.6.4 (v3.6.4:d48ecebad5, Dec 18 2017, 21:07:28) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> 7 * (6 * (5 * (4 * (3 * 4 + 1 - 4) + 4 - 5) + (3 * 4 + 1 - 4) - 6) + (4 * (3 * 4 + 1 - 4) + 4 - 5) - 7) + (5 * (4 * (3 * 4 + 1 - 4) + 4 - 5) + (3 * 4 + 1 - 4) - 6) - 8
7842
>>>