title: Recursive Procedure Whose Calls Resemble a Binary Tree in MIPS
body: <p>I'm working on an assignment and am having difficulty understanding how to properly code the following problem in C.</p>
  
  <pre><code>int choose(int n, int k){
      if (k == 0) {
          return 1;
      } else if (n == k) {
          return 1;
      } else if (n &lt; k) {
          return 0;
      } else {
          return choose(n-1, k-1) + choose(n-1, k);
      }
  }
  </code></pre>
  
  <p>My thoughts were to use three registers for storing the values onto the stack with each call <code>$s0, $s1, $s2</code>, where <code>$s0</code> will contain the value of updated <code>n</code>; <code>$s1</code> would maintain the value of <code>k</code>; and <code>$s2</code> would hold the value of <code>k</code> in the second <code>choose(n-1, k)</code> since that value will only decrease when the parent call changes it.  The reason I chose this is because the value of <code>k</code> isn't subtracted from each call in this one, it should be the same until the parent decrements it in a previous call.</p>
  
  <p>Here is the <code>Choose</code> procedure that I'm trying to do.  Problem is that I'm not getting the correct answer, of course.  </p>
  
  <pre><code>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
  </code></pre>
  
  <p>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.  </p>
  
  <p>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 <code>Choose(n,k)</code> and the children being <code>Choose(n-1, k-1) + Choose(n-1, k)</code> and once one of the leaf children branches from the <code>if</code> 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.  </p>
  
  <p>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.    </p>