You are to write a MIPS program that implement the following recursive function.
ID: 3665747 • Letter: Y
Question
You are to write a MIPS program that implement the following recursive function. f_i = 2f_i-1 + 4f_i-2; f_1 =3, f_0 = 1 Do not use any multiply instructions. You can implement the multiplication in any way you choose. You can assume that f is an integer and therefore 4 bytes in length. You must use syscall with appropriate parameters to read the value of i desired and to print out the result of the operation. Because this is a recursive function, you should use the stack in order to keep your function parameters from being overwritten with incorrect values. Before turning in your program, you should add comments to identify yourself and to clarify what is happening within the program itself. Comments can be created as in the sample below. Anything following the # is considered a comment until the end of line marker is reached.Explanation / Answer
We're going to implement a recursive function in MIPS. Recursion is one of those programming concepts that seem to scare students. One reason is that recursive functions can be difficult to trace properly without knowing something about how a stack works.
"Classic" recursion attempts to solve a "big" problem by solving smaller versions of the problem, then using the solutions to the smaller versions of the problem to solve the big problem.
"Classic" recursion is a divide-and-conquer method. For example, consider merge sorting. The idea behind merge sorting is to divide an array into two halves, and sort each half. Then, you "merge" the two sorted halves to sort the entire list.
Thus, to solve the big problem of sorting an array, solve the smaller problem of sorting part of an array, and use the solution of the smaller sorted array to solve the big problem (by merging).
How do you solve the smaller version of the problem? You break that smaller problem into even smaller problems, and solve those.
Eventually, you get to the smallest sized problem, which is called the base case. This can be solved without using recursion.
Recursion allows you to express solutions to a problem very compactly and elegantly. This is why people like using recursion.
However, recursion can use a lot of stack, and if you're not careful, you can overflow the stack.
For recursion to be successful, the problem needs to have a recursive substructure. This is a fancy term that says that to solve a big problem (say of size N), you should be able to solve a smaller problem (of smaller size) in exactly the same way, except the problem size is smaller.
As an analogy, you might have to, say, sweep the floor. Sweeping half the floor is the same as sweeping the entire floor, except you do it on a smaller area. A problem that is solved recursively generally needs to have this property.
Many folks think recursive functions are implemented in some weird and unusual way in assembly language. They can't believe it's implemented just like any other function.
The biggest misconception is that a function calls a smaller and smaller version, reaches the base case, then quits. For example, you might call fact(3), which calls fact(2), which calls fact(1), which finally calls fact(0), the base case.
Some programmers think the function stops there, right at the base case, and then jumps back to the initial recursive call. But you know that's not true.
Or do you? Suppose we have function f(), which calls function g(), and g() calls h().
What happens when we're done with h()? We return back to g(). And what happens when we're done with g()? We return back to f().
Recursive functions behave that way too! Thus, fact(3) calls fact(2) which calls fact(1) which calls fact(0), the base case. I call this phase the winding of the stack.
Once fact(0) is done, it goes back to fact(1), just like it would for non-recursive functions. When fact(1) is done, it goes back to fact(2). When fact(2) is done, it goes back to fact(3). When fact(3) is done, it goes back to whoever called fact(3). I call this the "unwinding" of the stack.
During the winding of the stack, you are making progress towards the base case. Basically, you're trying to get to the base case, solve the base case, and slowly grow your solution back as you go though the unwinding part of the recursion. Thus, winding heads to the solution of the base case, while unwinding typically grows the solution from base case back to the original call.
An Example
Let's solve the following recursive function, written in C. This sums all elements of an array.
A MIPS Translation
We assume arr is in $a0 and size is in $a1.
We have to decide what to save to the stack. We have two choices. Either save size - 1, from which we can compute arr[ size - 1 ], or save arr[ size - 1 ]. Let's opt to save size - 1 on the stack.
We must also save the return address, $ra since there is a function call. It's usually easy to tell whether to save the return address to the stack. If there's a function call, then save it.
As it turns out, we did't have to save size - 1. So we can leave that off the stack if you want. As a rule of thumb, you may end up deciding later on what to save and what not to save. A compiler, of course, has to determine this without being too clever. Sometimes a compiler might save too much to the stack, just so it's easier to generate code.
A few comments:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.