Understanding recursion with MIPS assembly language

Question

I was in class and we have/are covering recursion in Assembly Language. I felt like I understood recursion, but the more people attempt to explain it to me, the more I feel distant from it.

Anyways, our last slide had a function (in C?) and the teacher said he will cover it in class but call on us students to show the rest of the class on the board. I felt like he was looking at me the whole time and I am terrified of looking stupid.

Can you guys help me write this code in MIPS and help me understand it? IDK if this is too hard

Write in MIPS Assembly Language that to find fix(i,x), where fix(i, x) is defined recursively as:

int fix(int i, int x) // assume i > 0, x > 0
{
    if (x>0)
        return fix(i,x-1);
    else if (i>0)
        return fix(i-1, i-1)+1;
    else
        return 0;
}

Thank you guys, my class is tomorrow and I still hope he never calls on me; but I would like to actually understand this material.

NOTE: This will be an in class exercise with 0 credit attached. I feel like everyone in the class already knows how to do this.

Answer 1

While I am against just giving the answer to homework problems, here is the equivalent function that will find fix(i, x), complete with example call (this version is a little more efficient than the C version):

fix:
        bgtz RetI
        xor $v0, $v0, $v0
        jr $ra
RetI:
        move $v0, $a0
        jr $ra

# example of calling fix
main:
        la $a0, 42
        la $a1, 21
        jal fix

And let this be a lesson to you to learn what functions do before attempting to code them :)

Answer 2

Just break it into 3 pieces like the C above. Pass the values i and x via register and call yourself after running the if check and modifying the registers. The above shouldn't take more than 30ish lines of assembler to do. If I were a better MIPS coder, I would do it for you. It would look something like (is psuedo assembler)

fix:
  compare r0, 0
  branch greater than x_positive
  subtract r1,r1,1
  call fix
  return;
//  or just jump fix instead

x_positive:
  compare r1, 0
  branch greater than i_positive
  subtract r0, r0, 1
  subtract r1, r1, 1
  call fix
  return
// or just  jmp fix

i_positive:
  move return register, 0
  return

Funny thing is, this will always return 0 as written in C :)

  fix:
    move return_register, 0
    return

Answer 3

The assembly language has nothing to do with the recursion, that just happens to work due to the C language and the calling conventions and implementation. Just implement the C in assembler and dont care about recursion. I think I touched on this on a pet project http://github.com/dwelch67/lsasim unless I changed it out the last lesson is manually converting recursion in C to assembler. Its not mips so no worries about this being a homework problem.

Anyway the key to starting is to simply implement the C in assembly.

For example you have a function with input parameters.

int fix(int i, int x)

You will need to declare yourself a calling convention or use an existing one, to implement C this means you need some place for the input parameters, either push them on the stack or bring them in in registers. Assuming no optimization, you preserve these variables throughout the function and clean up at the end. So if you need to call ANY function to anywhere in the code (recursion, calling the same function, is a very small subset of ANY but falls into that category and IS NOT SPECIAL) you need to preserve these variables. IF the calling convention brings these in on the stack then you are already done, if the calling convention brings these in in registers then you need to preserve them before the call and restore after

push i
push x
implement call to function
pop x
pop i

and continue implementing the function.

that is it, the rest will take care of itself.

If you happen to notice that the function you created as an example, does not have a path where the input variables need to be preserved after the call to a function within this function. And the input variables are modified and used as inputs to the next call. so an optimization to your implementation of the C code would be to not worry about preserving those variables. simply modify them and pass them on. Using registers in the calling convention would be the simplest way to do this for this specific function. This is what a compiler would do anyway when optimizing (not preserve if using register based calling convention).

You could also do a tail optimization if that is what it is called. Normally when calling a function you use whatever the instruction normally does to perform a "call" which is different from a simple jump or branch because there is a return value kept somewhere. And there is some sort of return function that undoes this and returns back to the instruction after the call. nested calls mean nesting the return values, keeping track of all of them. IN this case though and other cases where the last thing you do the execution path of a function is call another function, you can instead (depends on the instruction set) branch to the function and not have to nest another set of return values. Looking at the arm instruction set for example:

Some code calls the first function:

bl firstfun:

In arm bl means branch link. register 14 will be filled in with the return value and the program counter will be filled in with the address to the function, firstfun.

typically if you need to call a function from a function you need to save r14 so you can return from that function, without this tail optimization:

firstfun:
 ...
 push {r14}
 bl secondfun
 pop {r14}
 bx r14
 ...
secondfun:
  bx r14

bx lr just means branch to the contents in r14 which in this case is the return. the optimization looks like this, it is important to note that in the first function the call to the second function is the last thing you do before returning from the first function. that is the key to this optimization.

firstfun:
 ...
 b secondfun
 ...
secondfun:
  bx r14

b just means branch, not a branch link simply modifies the pc and does not modify r14 or any other register or stack. The execution of the two implementations is the same functionally the outer function makes a call to firstfun and there is a return (bx r14) in the proper execution path.

Other folks have pointed out that this code may completely optimize itself into nothing since you return zero the original caller.

fix:
  return 0