I'm trying to code this recursive function into MIPS.
My problem is I'm not sure how I can do the recursive step.
I'm pretty sure I got the rest correct.
int recur(int n) {
if(n == 1 || n == 2) {
return 2;
} else {
return (n-4)+n*recur(n-2);
}
}
.data
promptMessage: .asciiz "Enter a number that is greater than or equal to 0: "
resultMessage: .asciiz "\nThe answer is: "
input: .word 0
answer: .word 0
.text
.globl main
main:
#Read the number from the user
li $v0, 4
la $a0, promptMessage
syscall
li $v0, 5
syscall
sw $v0, input
#Call the function
lw $a0, input
jal recur
sw $v0, answer
#Display result
li $v0, 4
la $a0, resultMessage
syscall
li $v0, 1
lw $a0, answer
syscall
.globl recur
recur:
addi $sp, $sp, -8
sw $a0, 0($sp)
sw $ra, 4($sp)
#Base Case if(n == 0 || n == 1) return 2;
li $v0, 2
beq $a0, $zero, DONE
beq $a0, 1, DONE
#RECURSIVE STEP
addi $a0, $a0, -2
jal recur
You did a great job. Creating C code first. You were very close.
I had to add the calculation step and the function epilog code.
Also, there was a bug where after main prints the number, there was no syscall 10 (exit) so the code would just fall through and recurse infinitely.
I reworked the C code slightly so it would be more compatible with the MIPS code.
Just for fun, and ease of testing, I changed main to loop and reprompt until it gets a negative number.
I've cleaned up and tested the code, added annotations [please pardon the gratuitous style cleanup]:
.data
# NOTE: these should appear first to maintain alignment to a 4 byte boundary
# (or the .align 4 will do it) otherwise, the lw/sw ops can fail on an
# alignment exception
.align 4
input: .word 0
answer: .word 0
promptMessage: .asciiz "Enter a number that is greater than or equal to 0 (-1 to stop): "
resultMessage: .asciiz "\nThe answer is: "
nl: .asciiz "\n"
.text .globl
main:
# prompt user
li $v0,4
la $a0,promptMessage
syscall
# Read the number from the user
li $v0,5
syscall
sw $v0,input
# negative value means stop
# NOTE: added this
bltz $v0,main_exit
# Call the function
lw $a0,input
jal recur
sw $v0,answer
# Display result message
li $v0,4
la $a0,resultMessage
syscall
# display number
li $v0,1
lw $a0,answer
syscall
# output newline
li $v0,4
la $a0,nl
syscall
# NOTE: this was added to allow multiple tries, but without it, there was
# the bug below
j main
# BUG: syscall to exit here was _missing_ so got fallthrough into "recur"
# causing the stack to overflow
main_exit:
li $v0,10
syscall
.globl recur
# recur -- recursion
#
# arguments:
# a0 -- the "n" value
#
# pseudo code:
# * int
# * recur(int n)
# * {
# * int r;
# *
# * if (n == 1 || n == 2) {
# * return 2;
# * }
# *
# * r = recur(n - 2);
# *
# * return (n - 4) + (n * r);
# * }
recur:
addi $sp,$sp,-8
sw $a0,0($sp)
sw $ra,4($sp)
# Base Case if(n == 0 || n == 1) return 2;
li $v0,2
beq $a0,$zero,recur_done
beq $a0,1,recur_done
# RECURSIVE STEP
addi $a0,$a0,-2 # n -= 2
jal recur
lw $a0,0($sp) # we need "n" back (not (n - 2))
# NOTE: this calculation was missing
mul $v0,$v0,$a0 # r *= n (i.e. (n * r))
addi $a0,$a0,-4 # n -= 4 (i.e. (n - 4))
add $v0,$v0,$a0 # sum them
# NOTE: this is the standard reversal for this function's stack prolog
recur_done:
lw $a0,0($sp)
lw $ra,4($sp)
addi $sp,$sp,8
jr $ra