Рекурсивная функция Фибоначчи в сборке mips

Question

Я новичок ie с мипсом Это часть домашнего задания, поэтому я думаю, вместо того, чтобы давать прямой ответ, указание на то, где что-то не так, может лучше всего понять для меня

Цель это преобразовать этот код C ++ в язык ассемблера mips

#fib(int n)
#{
#   if(n == 0)
#       return 0
#   else if ( n == 1)
#       return 1
#   else
#       return fib(n-1) +fib(n-2)
#n will be stored in a0 since it is the argument
#there will be two results, fib(n-1) and fib(n-2), store in the s0 and s1, so in the stack
#return the final value in $v0





addi $s2, $zero, 10
move $a0, $s2       #move the value of n to a0 to pass the argument
jal fib
beq $zero, $zero, END


fib: #fib code

addi $sp, $sp, -12  #reserve stack space for three variable needed to store in the stack
sw $ra, 0($sp)  #for return address store in stack
sw $s0, 4($sp)  #for results store in stack
sw $a0, 8($sp)  #for first result of fib(n-1) store in the stack

beq $a0, $zero, if0
beq $a0, 1, if1

#else if case
addi $a0, $a0, -1
jal fib
move $s0, $v0

lw $a0, 8($sp)
addi $a0, $a0, -2
jal fib
add $v0, $v0, $s0

lw $s0, 8($sp)
lw $ra, 0($sp)
addiu $sp, $sp, 12
jr $ra


if0:
lw $s0, 4($sp)
lw $ra, 0($sp)
addiu $sp, $sp, 12
li $v0, 0
jr $ra


if1:
lw $s0, 4($sp)
lw $ra, 0($sp)
addiu $sp, $sp, 12
li $v0, 1
jr $ra




END:
    nop

, однако результат не дает мне 55, когда n = 10 текущий результат, сохраненный в v0, дает мне значение 21. Может кто-нибудь помочь мне где я сделал точно не так? Заранее спасибо.

Answer 1

У вас есть опечатка в вашем первом возвращении:

lw $s0, 8($sp)

должно быть

lw $s0, 4($sp)

Answer 2

Это код, который я использовал до того, как он работал для меня. Вы можете использовать этот код в качестве основы и сравнить его с этим

.text
.align 2
.globl main

# Computes Fibonacci Sequence
# i =  0  1  2  3  4  5  6  7  8  9  10 ...
# x =  0  1  1  2  3  5  8 13 21 34  55 ...


main:
 la $a0, prompt
 li $v0, 4
 syscall    #Prompt for Int

 li $v0, 5
 syscall    #Response

 move $a0, $v0  #Move i to the $a0 register

 jal vfib

 add  $a0, $v0, $zero  #display Result
 li $v0, 1
 syscall

 li $v0, 10   #Exit Program
 syscall


vfib: 
 #Test Values
 addi $t0, $zero, 1  #Set $t0 to 1
 beq $a0, $zero, fib0 #Go to return 0 if i = 0
 beq $a0, $t0, fib1  #Go to return 1 if i = 1
 jr fib

fib0:
 li $v0, 0   #Return 0
 jr $ra

fib1:
 li $v0, 1   #Return 1
 jr $ra

fib:
 #Free Stack Space
 addi $sp, $sp, -16  #Make room for 4 elements in stack
     #$ra and i stored now, sums later
 sw $ra, 0($sp)  #Save return address
 sw $a0, 4($sp)  #Save i

 #Calculate (fib(n-1))
 addi $a0, $a0, -1  #Decrement i
 jal vfib   #recurse for (fib(n-1))
 sw $v0, 8($sp)  #Save value of (fib(n-1))

 #Calculate (fib(n-2))
 lw $a0, 4($sp)  #restore value of i from stack
 addi $a0, $a0, -2  #Decrement i twice
 jal vfib   #recurse for (fib(n-2))
 sw $v0, 12($sp)  #save result of (fib(n-2))

 #Restore from stack and sum
 lw $ra, 0($sp)  #Load return address
 lw $t0, 8($sp)  #load (fib(n-1))
 lw $t1, 12($sp)  #load (fib(n-2))
 addi $sp, $sp, 16  #free up 4 elements on stack
 add $v0, $t0, $t1  #Sum (fib(n-1) + fib(n-2))

 jr $ra

.data
prompt:  .ascii "Enter a non-negative integer: "