MIPS recursieve Fibonacci-reeks

Ik heb problemen met het recursief omgaan met stacks in MIPS. Ik snap het concept, maar mijn programma reageert niet zoals ik het bedoel.

Mijn doel is om gebruikersinvoer als n te nemen en het Fibonacci-getal af te drukken bij n. Wat ik tot nu toe heb, staat hieronder.

(Ik ben er vrij zeker van dat het probleem zit in de feitelijke berekening van het getal in de fib-functie.) Bedankt voor alle hulp! 🙂

.text
main:
# Prompt user to input non-negative number
la $a0,prompt
li $v0,4
syscall
li $v0,5
syscall
move $t2,$v0
# Call function to get fibonnacci #n
move $a0,$t2
move $v0,$t2
jal fib
move $t3,$v0
# Output message and n
la $a0,result
li $v0,4
syscall
move $a0,$t2
li $v0,1
syscall
la $a0,result2
li $v0,4
syscall
move $a0,$t3
li $v0,1
syscall
la $a0,endl
li $v0,4
syscall
# End program
li $v0,10
syscall
fib:
# Compute and return fibonacci number
beqz $a0,zero
beq $a0,1,one
sub $sp,$sp,4
sw $ra,0($sp)
sub $a0,$a0,1
jal fib
lw $ra,0($sp)
add $sp,$sp,4
sub $t8,$v0,2 # n - 2
sub $t9,$v0,1 # n - 1
add $v0,$t8,$t9 # add n-2,n-1
jr $ra # decrement/next in stack
zero:
li $v0,0
jr $ra
one:
li $v0,1
jr $ra
.data
prompt: .asciiz "Enter a non-negative number: "
result: .asciiz "F_"
result2: .asciiz " = "
endl: .asciiz "\n"

Voorbeelden van uitvoeringen:

Enter a non-negative number: 5
F_5 = -29
Enter a non-negative number: 6
F_6 = -61

Correcte uitvoeringen:

Enter a non-negative number: 5
F_5 = 5
Enter a non-negative number: 6
F_6 = 8

Antwoord 1, autoriteit 100%

Hier is een goed werkende code:

.text
main:
# Prompt user to input non-negative number
la $a0,prompt   
li $v0,4
syscall
li $v0,5    #Read the number(n)
syscall
move $t2,$v0    # n to $t2
# Call function to get fibonnacci #n
move $a0,$t2
move $v0,$t2
jal fib     #call fib (n)
move $t3,$v0    #result is in $t3
# Output message and n
la $a0,result   #Print F_
li $v0,4
syscall
move $a0,$t2    #Print n
li $v0,1
syscall
la $a0,result2  #Print =
li $v0,4
syscall
move $a0,$t3    #Print the answer
li $v0,1
syscall
la $a0,endl #Print '\n'
li $v0,4
syscall
# End program
li $v0,10
syscall
fib:
# Compute and return fibonacci number
beqz $a0,zero   #if n=0 return 0
beq $a0,1,one   #if n=1 return 1
#Calling fib(n-1)
sub $sp,$sp,4   #storing return address on stack
sw $ra,0($sp)
sub $a0,$a0,1   #n-1
jal fib     #fib(n-1)
add $a0,$a0,1
lw $ra,0($sp)   #restoring return address from stack
add $sp,$sp,4
sub $sp,$sp,4   #Push return value to stack
sw $v0,0($sp)
#Calling fib(n-2)
sub $sp,$sp,4   #storing return address on stack
sw $ra,0($sp)
sub $a0,$a0,2   #n-2
jal fib     #fib(n-2)
add $a0,$a0,2
lw $ra,0($sp)   #restoring return address from stack
add $sp,$sp,4
#---------------
lw $s7,0($sp)   #Pop return value from stack
add $sp,$sp,4
add $v0,$v0,$s7 # f(n - 2)+fib(n-1)
jr $ra # decrement/next in stack
zero:
li $v0,0
jr $ra
one:
li $v0,1
jr $ra
.data
prompt: .asciiz "This program calculates Fibonacci sequence with recursive functions.\nEnter a non-negative number: "
result: .asciiz "F_"
result2: .asciiz " = "
endl: .asciiz "\n"

Ik hoop nuttig te zijn

Adel Zare

adel.zare.63 [at] gmail [dot] com

Antwoord 2, autoriteit 44%

Het lijkt erop dat je het algoritme verkeerd hebt begrepen (of het gewoon verkeerd hebt geïmplementeerd). Wat je doet is dit:

int fib(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  int ret = fib(n - 1);
  return (ret - 2) + (ret - 1);
}

Wat u moetdoen, is dit:

int fib(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;
  return fib(n - 1) + fib(n - 2);
}