Assignment: Recursion in MIPS Assembly Programming In this assignment, you will be designing an assembly program running on MIPS hardware using the QtSpim MIPS simulator

For this assignment, you will learn Recursion, Call by Value, Call by Reference, Memory Systems along with activation record concept, parameter passing mechanisms, and recursive functions in terms of a program that computer a sum of the first n integers. A recursion is a function (or subroutine in assembly programing languages) which calls itself in its function body. The notion of recursion is important in Computer Science as a lot of definition is easier to be described by recursion. For example, the Fibonacci number is defined as the sum of the previous two Fibonacci numbers, i.e., Fibonacci(n) = Fibonacci(n-1)+Fibonacci(n-2). So as long as we define the initial values Fibonacci(0)=0 and Fibonacci(1)=1, we will compute Fibonacci(2)=1+0, Fibonacci(3)=1+1, etc. Similarly, we may define sum(n) = n+sum(n-1) and the initial value sum(0)=0. Note that we have to have initial values defined for a recursion relation. Otherwise, we may not compute all the values. These initial values in programing serve a return condition as well. Therefore, in order to compute sum(10), for example, we will need to computer sum(9). Again, in order to computer sum(9), we have to computer sum(8). This process continues until we reach sum(0), which is used to compute sum(1). From then on, the results will be popped back to answer the sum in the upper level. The sum function we are working on is a recursive function because it calls itself in its body with parameter n-1. Basically, a recursive function includes two parts: 1) return if initial condition is met, and 2) do computation with calls to the function itself. The pseudo code for the sum function is depicted below. function sum(n) { // determine when to return if (n<1) return 0; else // do computation; call itself return n*sum(n-1); } Each function call will yield a call instance, which is unique in the system, and requires a data structure, called activation record, that contains return address, parameters, return value, and others. The return address will be the address of the next instruction following the call statement. The parameters will be values passed to the function. The return value will be the result to be 2 returned to the caller. There are two basic types of parameter passing mechanisms in most systems: call by value and call by reference. Call by value will pass the actual values to the function for computation whereas call by reference will pass the address (reference) for the value stored. Typically, we use call by reference for passing an array. In this assignment, we will use the following activation record for the recursive sum function as follows: Table 1 Activation Record for the Sum(n) Function Top of the stack Parameter n This is a caller saved variable using call by value to be passed to the sum function. This slot will also be used to store the result returning to the caller. Return Address The system will save the return address after the instruction JAL is executed. The address is the next instruction following the JAL instruction. Bottom of the stack Local variable ($S0) This is callee saved variable used locally for the sum function. So the callee should pop it up before returning back to caller. 1. Make a new folder for all your assembly program files. Create a file using Notepad or any editor available in your computer and name it Assignment-sum-. The implementation of the sum function in assembly programming involves maintaining the activation record in addition to the program logic (pseudo code). Basically, the structure is quite standard as callee must save registers or local variables in the stack at the beginning and restore them right before returning (jr $ra). function sum(n) { // save registers or local variables used // determine when to return // save return address // do computation; call itself // restore registers or local variables // return to caller } 3 A rule of thumb is to keep the stack size balanced, i.e., the stack size will not change before and after a function call. The number of stack slots saved before a function is performing its computation should be restored with the exact amount of slots in reversed order. Otherwise, it will cause some issues like memory leak! 2. We use jal sum to call a subroutine. Implementation of the sum function in between the sw and addi to implement push and pop instruction, respectively. You also need to maintain stack pointers yourself. Since you have saved $S0, you can freely use it any way you like. You dont want to use other registers as they may be used by other functions or even the function itself. So your implementation for the sum function is simply an if-thenelse statement in assembly programming. If the initial condition is met (n==1), the recursive call will stop. Otherwise it will call the function itself for the instance sum(n-1). When a recursive call is needed, the implementation will create another action record, right before the current one. So the parameter n-1 will be passed to the next action record by pushing it to the stack. You may review the assembly implementation for the if-then-else structure in previous assignments or in the lecture slides. Implement the sum function and test it using the following values. 1) Test sum(2) by passing #2 before the recursive call 2) Test sum(10) by passing #10 before the recursive call 3) Test sum(100) by passing #100 before the recursive call check What to submit? Your MIPS assembly program and a screenshot of the above tests.