Pretty good effort.
To answer your question: you can simply establish a stack frame at function entry and restore from it at the end.
I did have to repurpose $s0 slightly to store an intermediate value and add it to the stored values in the stack frame (i.e. stack frame is now 3 words instead of 2).
Anyway, here's the corrected code. I've tried to annotate it a bit (IMO, in asm, there's no such thing as "too many comments") [please pardon the gratuitous style cleanup]:
.data
prompt1: .asciiz "Enter the value for the recursive function f(n) = 2f(n-1)+3f(n-2)+1: "
prompt2: .asciiz "Result: "
numberEntered: .word 0
answer: .word 0
.text
main:
# Ask for the value
li $v0,4
la $a0,prompt1
syscall
# enter value
li $v0,5
syscall
sw $v0,numberEntered # stores the number
# call the function
lw $a0,numberEntered
jal function
sw $v0,answer
# Print out the result
li $v0,4
la $a0,prompt2
syscall
lw $a0,answer
li $v0,1
syscall
li $v0,10
syscall
.globl function
# function -- calculation
# v0 -- return value
# a0 -- current n value
# s0 -- intermediate result
function:
subi $sp,$sp,12 # establish our stack frame
sw $ra,8($sp) # save return address
sw $a0,4($sp) # save n
sw $s0,0($sp) # save intermediate result
# base case
# NOTE: with the addition of n-2, the "beq" was insufficient
li $v0,1
ble $a0,$zero,done
# calling f(n-1)
sub $a0,$a0,1 # get n-1
jal function
# NOTE: these could be combined into a single instruction
mul $v0,$v0,2 # get 2f(n-1)
move $s0,$v0 # save it
# calling f(n-2)
sub $a0,$a0,1 # get n-2
jal function
mul $v0,$v0,3 # get 3f(n-2)
# get 2f(n-1) + 3f(n-2) + 1
add $v0,$s0,$v0
add $v0,$v0,1
done:
lw $ra,8($sp) # restore return address
lw $a0,4($sp) # restore n
lw $s0,0($sp) # restore intermediate result
addi $sp,$sp,12 # pop stack frame
jr $ra # returns
UPDATE:
This solution is way simpler than I thought it would be.
That may be because of the way a stack frame is done in asm [or C].
Consider a modern C program:
int
whatever(int n)
{
int x;
// point A
x = other(1);
// do lots more stuff ...
{
// point B
int y = other(2);
// do lots more stuff ...
// point C
n *= (x + y);
}
// do lots more stuff ...
n += ...;
return n;
}
The C compiler will establish a stack frame upon entry to whatever that will reserve space for x and y even though y is only set much later. Most C programmers don't realize this.
In interpreted languages (e.g. java, python, etc.) space for y isn't reserved until the code at point B is executed. And, they will [usually] deallocate it when y goes "out of scope" [after point C].
Most C programmers think that having a scoped declaration [like y] saves on stack space. (i.e.) In the scoped block, the compiler would increase the stack frame size to accomodate y and shrink it again when y is no longer needed.
This is simply not correct. The C compiler will set up the stack frame and reserve space for all function scoped variables even if they're declared late in the function or inside an inner scope [like y].
This is just what we did in your function. This is true even though we didn't need/utilize the stack space [at offset 0] for $s0 until the middle of the function.
So, I'm guessing that your experiences with other languages that do reserve space dynamically [effectively] or the common wisdom about C may have led you to a more complex model of what you thought was required. Hence your original question: Do I have to "wind up" the stack twice?
I should also mention that the calling convention of function is not ABI conforming. This is perfectly fine if it's self contained (i.e. does not call anything else). That is, in asm, for "leaf" functions, we can define whatever we wish.
The reason is that $a0 call be modified/trashed by callee. We saved/restored it from the stack, but calling another function might mess things up. The remedy would simply be to use another register to preserve the value [or save/restore to an extra place in the stack frame], so a bit more work if function ends up calling something else.
