MIPS-Rekursive Fibonacci-Folge

Ich habe Probleme beim Umgang mit stacks rekursiv in MIPS. Ich einen Begriff davon bekommen, aber mein Programm nicht reagiert wie ich meine es zu.

Mein Ziel ist es, Benutzereingaben als n, und drucken Sie die Fibonacci-Zahl zu n ist. Was ich habe, so weit unten ist.

(Ich bin mir ziemlich sicher, dass das problem in der tatsächlichen Berechnung der Anzahl der fib-Funktion.) Vielen Dank für jede Hilfe!!! 🙂

.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"

Beispiel läuft:

Enter a non-negative number: 5
F_5 = -29

Enter a non-negative number: 6
F_6 = -61

Richtig läuft:

Enter a non-negative number: 5
F_5 = 5

Enter a non-negative number: 6
F_6 = 8
  • 5 gibt -29. 6 gibt -61. etc.
InformationsquelleAutor Ethan | 2014-04-10
  1. 5

    Hier eine einwandfrei funktionierende 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"

    Hoffen, nützlich sein

    Adel Zare

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

    • add $sp,$sp,4 sub $sp,$sp,4 #Push return value to stack. Können Sie erklären, diese zwei Zeilen
    InformationsquelleAutor user3611133
  2. 4

    Anscheinend haben Sie das falsch verstanden, die Algorithmus (oder nur implementiert, ist es falsch). Was du tust, ist dies:

    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);
}

    Was Sie sollte tun, ist dies:

    int fib(int n) {
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;

  return fib(n - 1) + fib(n - 2);
}
    InformationsquelleAutor Michael
Schreibe einen Kommentar