Recursive Procedure Whose Calls Resemble a Binary Tree in MIPS

Question

I'm working on an assignment and am having difficulty understanding how to properly code the following problem in C.

int choose(int n, int k){
    if (k == 0) {
        return 1;
    } else if (n == k) {
        return 1;
    } else if (n < k) {
        return 0;
    } else {
        return choose(n-1, k-1) + choose(n-1, k);
    }
}

My thoughts were to use three registers for storing the values onto the stack with each call $s0, $s1, $s2, where $s0 will contain the value of updated n; $s1 would maintain the value of k; and $s2 would hold the value of k in the second choose(n-1, k) since that value will only decrease when the parent call changes it. The reason I chose this is because the value of k isn't subtracted from each call in this one, it should be the same until the parent decrements it in a previous call.

Here is the Choose procedure that I'm trying to do. Problem is that I'm not getting the correct answer, of course.

Choose:
    #store current values onto stack
    addi $sp, $sp, -16
    sw $ra, 0($sp)
    sw $s0, 4($sp)
    sw $s1, 8($sp)
    sw $s2, 12($sp)

    #check values meet criteria to add to $v0       
    beq $s1, $0, one
    beq $s0, $s1, one
    blt $s0, $s1, zero
    beq $s2, $0, one

    #no branches passed so decrement values of n and k
    subi $s0, $s0, 1
    subi $s1, $s1, 1

    #move values of registers to $a's for argument passing
    move $a0, $s0
    move $a1, $s1

    jal Choose  #call procedure again

    #this is where I'm having my problems
    #not sure how to loop the procedure to get
    #the second half of the equation Choose(n-1,k)
    #which is the reason for the next 2 lines of code
    move $a2, $s2
    jal Choose

    add $v0, $v0, $v1
    j Choose_Exit


#add one to $v1 from branch passed
one:
    addi $v1, $v1, 1
    j Choose_Exit

#branch returns 0   
zero:
    addi $v1, $v1, 0
    j Choose_Exit

#return values to caller from stack
Choose_Exit:
    lw $s2, 12($sp)
    lw $s1, 8($sp)
    lw $s0, 4($sp)
    lw $ra, 0($sp)
    addi $sp, $sp, 16
    jr $ra

So I'm having a problem understanding how to properly implement this recursive procedure twice to add them together. I can understand how to create a recursive procedure in MIPS to perform a factorial, since that is always the definition of recursion for any language. But using recursion with differing arguments and then add them all together is confusing me to no end.

When written out on paper, I understand that this procedure can be represented by a binary tree of parents and children. The parent being the single function Choose(n,k) and the children being Choose(n-1, k-1) + Choose(n-1, k) and once one of the leaf children branches from the if statement, it passes a digit to the parent who will wait for the other callee portion of the addition to return its value, etc etc etc.

Any help to point me in the correct direction as to what I'm doing wrong with my approach would be great. I understand the beginning, I understand the end, just need some assistance to help understand the most important part of the middle.

Answer 1

You were pretty close.

You established your stack frame with four words for: return address, arg1, arg2, and save for return value.

Your main snag was that after the first call to your function, you have to save the $v0 onto the stack [as Margaret mentioned above].

Here's some code that I believe will work. It is very similar to yours, but I wrote it from scratch. It has the correct "push"/"pop" of the first call's return value.

I did add one small optimization for the early escape [non-recursive] cases: they omit creating the stack frame.

Anyway, here it is:

#@+
#   int
#   choose(int n, int k)
#   {
#
#       if (k == 0)
#           return 1;
#
#       if (n == k)
#           return 1;
#
#       if (n < k)
#           return 0;
#
#       return choose(n - 1,k - 1) + choose(n - 1,k);
#   }
#@-

    .text

# choose -- choose
#
# RETURNS:
#   v0 -- return value
#
# arguments:
#   a0 -- n
#   a1 -- k
#
# registers:
#   t0 -- temp for 1st return value
choose:
    beqz    $a1,choose_one          # k == 0? if yes, fly
    beq     $a0,$a1,choose_one      # n == k? if yes, fly
    blt     $a0,$a1,choose_zero     # n < k? if yes, fly

    # establish stack frame (preserve ra/a0/a1 + space for v0)
    sub     $sp,$sp,16
    sw      $ra,12($sp)
    sw      $a0,8($sp)
    sw      $a1,4($sp)

    addi    $a0,$a0,-1              # get n - 1 (common to both calls)

    # choose(n - 1,k - 1)
    addi    $a1,$a1,-1              # get k - 1
    jal     choose
    sw      $v0,0($sp)              # save 1st return value (on _stack_)

    # choose(n - 1,k)
    addi    $a1,$a1,1               # get k (from k - 1)
    jal     choose

    lw      $t0,0($sp)              # "pop" first return value from stack
    add     $v0,$t0,$v0             # sum 1st and 2nd values

    # restore from stack frame
    lw      $ra,12($sp)
    lw      $a0,8($sp)
    lw      $a1,4($sp)
    add     $sp,$sp,16
    jr      $ra                     # return

choose_one:
    li      $v0,1
    jr      $ra

choose_zero:
    li      $v0,0
    jr      $ra

---

UPDATE:

First off, I like how you noted the procedure as you did before you called it. I'm going to steal that!

Be my guest! It's from many years of writing asm. For a primer on my thoughts about how to write asm well, see my answer: MIPS linked list

I've tried this and it works. I need to experiment with your code to understand why the stack is manipulated when it is (always thought it had to be at the very beginning and end of a proc).

Normally, the stack frame is established at the proc start and restored from at the proc end. Your code for handling the "quick escape" [non-recursive] cases was correct, based on having already established the frame.

This was just a small optimization. But, it comes from the fact that because mips has so many registers that, for small functions, we don't even need a stack frame, particularly if the function is a "leaf" or "tail" (i.e. it doesn't call any other function).

For smaller [non-recursive] functions, sometimes we can get away with a one word stack frame that just preserves $ra (e.g.): fncA calls fncB, but fncB is a leaf. fncA needs a frame but fncB does not. In fact, if we control both functions and we know that fncB does not modify a given temp register (e.g. $t9), we can save the return address there instead of creating a stack frame in fncA:

fncA:
    move    $t9,$ra                 # preserve return address
    jal     fncB                    # call fncB
    jr      $t9                     # return

fncB:
    # do stuff ...
    jr      $ra                     # return

Ordinarily, we couldn't rely upon fncB preserving $t9 because, according to the mips ABI, fncB is at liberty to modify/trash any register that is not $sp or $s0-$s7. But, if we craft the functions such that we consider fncB to be "private" to fncA (e.g. like a C static function that only fncA has access to), we can do whatever we want.

Believe it or not, fncA above is ABI conforming.

A given callee (e.g. fncA) does not need to preserve $ra for [the sake of] its caller, just for itself. And, what is important is the value inside $ra, not the specific register. A callee only needs to preserve $s0-$s7, ensure that $sp has the same value at exit as entry, and that it returns to the correct address in caller [which the jr $t9 does--because it has the value that was in $ra when fncA was called].

I like your use of the temp register.

An extra register is required because, in mips, we can not do arithmetic operations from memory operands. mips can only do lw/sw. (i.e.) There is no such thing as:

    add     $v0,$v0,0($sp)

I used $t0 for simplicity/clarity because, when you need a temp reg, $t0-$t9 are the usual ones to use. The code "reads better" when using $t0.But, this is just a convention.

In the mips ABI, $a0-$a3 can be modified, as can $v1 as only $s0-$s7 need to be preserved. And, "modification" means that they can be used to hold any value or used for any purpose.

In the above link, note that strlen increments $a0 directly to find the end of the string. It is using $a0 for a useful purpose, but, as far as the caller to it is concerned, $a0 is being "trashed" [by strlen]. This usage is ABI conforming.

In choose, I could have used just about any register: $v1, $a2-$a3 instead of $t0. In fact, at that particular point in choose, $a0 is no longer needed, so it could have been used in place of $t0. Although for choose, we are non-ABI conforming (because we save/restore $a0-$a1), this would work in choose, because we restore the original value of $a0 from the function epilog [stack frame pop], preserving the recursive nature of the function.

As I said, $t0-$t9 are the usual registers to use for scratch space. But, I've written functions that use all 10 of them, and still needed more (e.g. drawing into a frame buffer using the Bresenham circle algorithm). $v0-$v1 and $a0-$a3 can be used as temp regs to get an additional 6. If necessary, $s0-$s7 can be preserved in the stack frame, solely to free them up to use as more temp regs.

Answer 2

Disclaimer: I rewrite the assembly code WITHOUT checking it.

1. There are delay-slots to consider so better to make smart use of them and to make them explicit to avoid aggregations of implicit nop instructions after branch instructions.
2. Reverse the order of calls between choose(n - 1,k - 1) and choose(n - 1,k) for smarter usage of $a0 and $a1 and of the stack.
3. Restrain stack usage for only calling choose(n - 1,k) and use tail calling for calling choose(n - 1,k - 1).
4. It makes more sense to stack the value of a0-1 and not a0.
5. We accumulate everything into $v0 instead of stacking it. We keep $t0 as a local result to add to $v0 because it is cheap while we can discard it by doing direct things with $v0.
6. As a result, the overall changes should make icache happier with less instructions and dcache happier with less stack space.

The assembly code:

#@+
#   int
#   choose(int n, int k)
#   {
#
#       if (k == 0)
#           return 1;
#
#       if (n == k)
#           return 1;
#
#       if (n < k)
#           return 0;
#
#       return choose(n - 1,k - 1) + choose(n - 1,k);
#   }
#@-

    .text

# choose -- choose
#
# RETURNS:
#   v0 -- return value
#
# arguments:
#   a0 -- n
#   a1 -- k
#
# registers:
#   t0 -- temp for local result to accumulate into v0
choose:
    j       choose_rec
    addui   $v0, $zr, 0             # initialize $v0 to 0 before calling
choose_rec:
    beqz    $a1,choose_one          # k == 0? if yes, fly
    addui   $t0,$zr,1               # branch delay-slot with $t0 = 1
    beq     $a0,$a1,choose_one      # n == k? if yes, fly
    nop                             # branch delay-slot with $t0 = 1 already done
    blt     $a0,$a1,choose_zero     # n < k? if yes, fly
    addui   $t0,$zr,0               # branch delay-slot with $t0 = 0

    # establish stack frame (preserve ra/a0/a1)
    sub     $sp,$sp,12
    addui   $a0,$a0,-1              # get n - 1 (common to both calls)
    sw      $ra,8($sp)
    sw      $a0,4($sp)          
    jal     choose_rec              # choose(n - 1,k)
    sw      $a1,0($sp)

    # restore from stack frame
    lw      $ra,8($sp)
    lw      $a0,4($sp)
    lw      $a1,0($sp)
    add     $sp,$sp,12

    # choose(n - 1,k - 1)
    j       choose_rec              # tail call: jump instead of call
    addi    $a1,$a1,-1              # get k - 1

choose_one:
choose_zero:
    jr      $ra                     # return   
    addui   $v0,$v0,$t0             # branch delay-slot with $v0 += $t0