Fibonacci recursion function in Mips

0

I am trying to pratice how recursion works in Mips. So I tried to write a fibonacci function fib. At first I had addi $a0, $a0, n to write a general solution, but I thought that if I want to check my results in Qtspim , maybe i need to add a real number as an argument. I do not want a full answer , if the thought behind the code is wrong, but some help in order to run it in Qtspim, and find my mistakes (logic mistakes) on my own
This is my code:

.globl main
    .text
    main:
addi $a0, $a0, 4


fib:
addi $sp, $sp, -8
sw $ra, 4($sp) 
sw $a0, 0($sp) 
slti $t0, $a0, 1
beq $t0, 1, L2  #if n<1     
beq $a0, 1, L2  # if n=1
beq $t0, 0, L1 # if n>1

#what to do when n<=1
L2:
addi $v0, $v0, 1 
jr $ra 

#what to do when n>1
L1: 
addi $a0, $a0, -1 
jal fib
lw $a0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
lw $t1, 0($v0)
add $v0, $t1, $v0
jr $ra

li $v0,10
syscall

I get an error message as such: Bad address in data/stack read: 0x00000000

recursion
mips
qtspim
asked on Stack Overflow Oct 31, 2020 by brucebanner • edited Oct 31, 2020 by brucebanner

2 Answers

1
    .text
    main:
addi $a0, $a0, 4
#### you've place fib inline inside main,
#### you should have all of main here, and "call" fib using jal instruction  
#### and the syscall for exit goes up here as well

fib:
addi $sp, $sp, -8        # you will want one more word of stack space
sw $ra, 4($sp) 
sw $a0, 0($sp) 
slti $t0, $a0, 1            # i would have use 2 here instead of 1
beq $t0, 1, L2  #if n<1     # this is ok, but better to use bne $t0, $0, L2
beq $a0, 1, L2  # if n=1    # and then this would not be needed
beq $t0, 0, L1 # if n>1     # this doesn't need to be conditional, if the program reaches here then L1 is the thing to do next.

#what to do when n<=1
L2:
addi $v0, $v0, 1            # here you want to return just 1 not v0+1
jr $ra 

#what to do when n>1
L1: 
addi $a0, $a0, -1 
jal fib                        # fib(n-1), good
lw $a0, 0($sp)                 # this reloads $a0 the original n
lw $ra, 4($sp)
addi $sp, $sp, 8
lw $t1, 0($v0)                 # after a call to fib $v0 holds fib(n)
                               # an integer value but you're treating it like a pointer and dereferencing it
add $v0, $t1, $v0              # here doing fib(n-1) + n
                               # you want fib(n-1) + fib(n-2) instead
                               # so you're missing a fib(n-2)
jr $ra

li $v0,10                  # this is part of main, so move it to where main is
syscall                    # realize that code located here is unreachable (aka dead)
                           # anything after an unconditional branch (here the jr $ra just above)
                           # and without a label is very suspicious as unreachable
answered on Stack Overflow Oct 31, 2020 by Erik Eidt • edited Oct 31, 2020 by Erik Eidt
0

update , some improved (i hope ) code

    .globl main
.text
main:
addi $a0, $a0, 4
jal fib 
li $v0, 10
syscall 

fib:
addi $sp, $sp, -8
sw $ra, 4($sp) 
sw $a0, 0($sp) 
slti $t0, $a0, 2
beq $t0, 1, L2      

#what to do when n<=1
L2:
addi $v0, $v0, 1 
jr $ra 

#what to do when n>1
L1: 
addi $a0, $a0, -1  # a0 -> n-1
jal fib   # fib(n-1)
lw $a0, 0($sp) #load word from memory adress 0($sp) to register $a0
lw $ra, 4($sp)  #load word from memory adress 4($sp) to register $ra
addi $sp, $sp, 8 
add $t1, $zero, $v1  # in register $t1 store current $v1
add $v0, $t2, $v0  # v0_ n+1 =v0 _n + v0_n-1
add $t2, $t1, $zero  # in $t2 save the previous value of v1 

   
answered on Stack Overflow Nov 3, 2020 by brucebanner • edited Nov 4, 2020 by brucebanner

User contributions licensed under CC BY-SA 3.0