= Solution
Use the conventional <integer> <calling convention>: `$a0` holds the argument and `$v0` holds the result. The function is recursive, so every call must preserve its own <return address> and original argument. The first recursive result must also survive the second call; a <caller-saved register> alone would not protect it.
This implementation reserves a 32-<byte> <stack frame>, keeping the <stack pointer> eight-<byte> aligned. Offsets 0–15 are available as the outgoing argument area, 16 stores the original argument, 20 stores the first result, 24 is padding, and 28 stores the <return address>. It changes no <callee-saved register>. Assemble in classic MIPS delayed-branch mode with instruction reordering disabled, such as `.set noreorder`.
``
foo:
addiu $sp,$sp,-32 # allocate 32-byte aligned frame
sw $ra,28($sp) # save caller return address
sw $a0,16($sp) # save original n
beq $a0,$zero,foo_base
sll $zero,$zero,0
addiu $t0,$zero,1
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $t0,$zero,2
beq $a0,$t0,foo_base
sll $zero,$zero,0
addiu $a0,$a0,-1
jal foo
sll $zero,$zero,0
sw $v0,20($sp) # preserve foo(n-1) across next call
lw $a0,16($sp) # recover original n
sll $zero,$zero,0
addiu $a0,$a0,-3
jal foo
sll $zero,$zero,0
lw $t0,20($sp)
sll $zero,$zero,0
addu $v0,$v0,$t0 # combine the two recursive results
beq $zero,$zero,foo_return
sll $zero,$zero,0
foo_base:
addu $v0,$a0,$zero # base case result is n
foo_return:
lw $ra,28($sp)
sll $zero,$zero,0
addiu $sp,$sp,32 # release the frame
jr $ra
sll $zero,$zero,0
``
All displayed operation mnemonics denote single <machine instructions>. In particular, `sll $zero,$zero,0` is the actual harmless shift encoding often abbreviated by the <pseudoinstruction> `nop`; `addu $v0,$a0,$zero` performs a copy without the `move` <pseudoinstruction>. Each branch or jump has an explicit harmless <branch delay slot>, and harmless shifts also separate loads from their subsequent uses. The base cases return the original argument; other calls return the sum of the two recursive values. Every return restores the saved <return address> and exactly undoes the stack allocation.<MIPS32 Architecture For Programmers Volume II by MIPS Technologies>[Revision 2.00, ADDIU and ADDU, pp. 37–38; JAL and JR, pp. 139 and 144]{ref}
The stated domain is <nonnegative integer> $n$, with sufficient stack space and a result representable in the intended <integer> type. The non-trapping additions implement that mathematical result within range; beyond it, machine wraparound would require a separately specified <integer> semantics.
Back to article page
