MIPS遞歸斐波那契數列

我無法在MIPS中遞歸處理堆棧。我明白了這個概念，但是我的程序並沒有像我的意思那樣反應。MIPS遞歸斐波那契數列

我的目標是將用戶輸入作爲n並在n處打印斐波那契數。我到目前爲止已經在下面。

（我相當確定問題是在實際計算fib函數中的數字。）感謝您的幫助！ :)

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

示例運行：

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

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

正確運行：

Enter a non-negative number: 5 
F_5 = 5 

Enter a non-negative number: 6 
F_6 = 8

來源

2014-04-10 Ethan

5返回-29。 6返回-61。等 – Ethan

你似乎誤解了該算法（或只是實現它不正確）。你在做什麼是這樣的：

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

你應該做的是：

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

    return fib(n - 1) + fib(n - 2); 
}

來源

2014-04-10 13:19:52 Michael

這是一個正常工作代碼：

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

希望能有用

Adel Zare

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

來源

2015-05-13 20:23:34 user3611133

'''添加$ sp，$ sp，4 sub $ sp，$ sp，4 #Push返回堆棧的值''。你能解釋這兩條線嗎？ –

MIPS遞歸斐波那契數列

回答

相關問題