How to write recursive functions in MIPS assembler

This is a short document that provides some hints on how to write recursive functions in MIPS assembler.

1. Start by writing a Java version of the functions (methods) that you want to implement. You should use the Java version to verify that your implementation works correctly before you start writing in assembler. You should also use the Java program as an aid for debugging the assembler program.
2. Instrument the Java program to provide you with simple tracing capability. Add to each function print statements that print out the function name and the input parameters. Generate a small trace file.
3. When you write the assembler version of the function, make sure that it is functionally identical to the Java program. It is important to make sure that the function call sequence in the assembler version is identical to the function call sequence in the Java program. Use a trace of the Java call sequence to figure out the function call order.
4. When writing the assembler version of a function it is important to follow the following steps:
   • First allocate a stack frame that is large enough to hold all the values that you need to store in the stack. It is OK to make the stack frame larger then you need.
   • Save the $ra register on the stack.
   • Save the input registers $a0, $a1, . . . on the stack.
   • Save any the value of any $s registers that your function uses on the stack.
   • Make sure that the content of a register that might be modified (for example a $a register or a $v register) when the you make a function call is saved before you make the function call. The value should be saved on the stack or in a $s register.
   • When you need to use a value that is a formal parameter to a recursive function, get it out of the stack. It is not safe to assume that a value in a $a register stay unmodified after you called a function.
   • Make sure that the first four function parameters are loaded into $a0, ... $a3 before you call the function.
   • Make sure that the parameters are loaded in the right order, first parameter in $a0, second parameter in $a1, etc.
   • Before exiting from a function make sure that $v0 is loaded with the value that the function returns.
   • Before exiting from the function make sure to restore the $s registers (if they are used) and the $ra register.
   • Don't forget to pop the stack frame before the function exit.
5. You are provided with few simple examples of recursive functions, study these functions. Run the factorial function with a small input value and single step it so you could see how it works.
6. Once you are done with writing the assembler version, debug it on small examples first.
7. If you need to, "step" the code to see that the sequence of function calls is the same as the one generated by the Java program. Use breakpoints at the entry of each function and check that the values passed in the $a registers match the parameter values that are passed in the Java program.
8. If you need to, add tracing code into your assembler functions that prints out the function name and the function input-parameters values.
9. It is useful to use the editor "cut and paste" facility when you have repeating code.
10. Make sure to comment every line. Your comments should reflect what the instructions are doing.