Question

Write a MIPS assembly program to calculate the Fibonacci numbers from 1..n using the recursive method. The definition of a Fibonacci number is F(n) = F(n-1) + F(n-2).

The implementation must follow the following guidelines:

• Prompt the user for a number n
• Allocate heap memory to hold the exact number of elements in the Fibonacci sequence for n
• Implement recursive Fibonacci method as a subprogram
• Print the Fibonacci sequence array

Answer 1

Code:

.text
main:
# Prompt user to input
la $a0,askUser
li $v0,4
syscall

li $v0,5    #Read the number
syscall
move $t7,$v0    # move number to t7

# Call function to get fibonnacci sum
move $a0,$t7
move $v0,$t7
jal fibbonacciSum     #call fibbonacciSum
move $t6,$v0    #store result in t6

la $a0,res   #Print output prompt
li $v0,4
syscall

move $a0,$t7    #Print sum
li $v0,1
syscall

la $a0,res2 #Print output prompt
li $v0,4
syscall

move $a0,$t6    #Print the answer
li $v0,1
syscall

la $a0,endl
li $v0,4
syscall

# Exit
li $v0,10
syscall

fibbonacciSum:

beqz $a0,zero   # return 0 if n=0
beq $a0,1,one   # return 1 if n=1

sub $sp,$sp,4   #storing return address on stack
sw $ra,0($sp)

sub $a0,$a0,1
jal fibbonacciSum     #fibbonacciSum(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)

sub $sp,$sp,4   #storing return address on stack
sw $ra,0($sp)

sub $a0,$a0,2
jal fibbonacciSum     #fibbonacciSum(n-2)
add $a0,$a0,2

lw $ra,0($sp)   #restoring return address from stack
add $sp,$sp,4

lw $s0,0($sp)   #Pop return value from stack
add $sp,$sp,4

add $v0,$v0,$s0 # fibbonacciSum(n-1)+fibbonacciSum(n-2)
jr $ra

zero:
li $v0,0
jr $ra
one:
li $v0,1
jr $ra

.data
askUser: .asciiz "Enter a number: "
res: .asciiz "Fibonacci Sum for "
res2: .asciiz " is "
endl: .asciiz "\n"