recursion - MIPS 递归斐波那契数列

Question

我在 MIPS 中递归处理堆栈时遇到问题。我明白了这个概念，但我的程序没有按照我的意思使用react。

我的目标是将用户输入作为 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

Answer 1

这是一个正常工作的代码:

.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.63 [at] gmail [dot] com