CS 2734 Computer Organization II

Laboratory 6 [2/22; 2/24; 3/1] Implementing recursive functions in MIPS (Comb, Hanoi, or Writebase)

This laboratory asks you to implement one of three different recursive functions in the MIPS assembler language.

If your SSN has last 2 digits in the range 0-33 then write Hanoi below

else if your SSN has last 2 digits in the range 34-66 then write Comb below

else if your SSN has last 2 digits in the range 67-99 then write Writebase below

For those doing Hanoi (SSN, last 2 digits: 0-33), here is that program in C:

       /* Tower of Hanoi problem: given n discs of decreasing size
        * on a peg numbered 1, show how to move them all to peg
        * number 2, using peg number 3.  The rules state that you
        * must not place a disc on a smaller disc, though you can
        * place a disc on an empty peg or on a larger disc.
        */
       #include <stdio.h>

       void hanoi(int n, int start, int finish, int extra);

       void main(void)
       {
          int n;
          scanf("%d", &n);
          hanoi(n, 1, 2, 3);
       }

       void hanoi(int n, int start, int finish, int extra)
       {
          if (n != 0) {
             hanoi(n-1, start, extra, finish);
             printf("Move disc %d from %d to %d.\n", n, start, finish);
             hanoi(n-1, extra, finish, start);
          }
       }

Along with sample output:

       4
       Move disc 1 from 1 to 3.
       Move disc 2 from 1 to 2.
       Move disc 1 from 3 to 2.
       Move disc 3 from 1 to 3.
       Move disc 1 from 2 to 1.
       Move disc 2 from 2 to 3.
       Move disc 1 from 1 to 3.
       Move disc 4 from 1 to 2.
       Move disc 1 from 3 to 2.
       Move disc 2 from 3 to 1.
       Move disc 1 from 2 to 1.
       Move disc 3 from 3 to 2.
       Move disc 1 from 1 to 3.
       Move disc 2 from 1 to 2.
       Move disc 1 from 3 to 2.

For those doing Comb (SSN, last 2 digits: 34-66), here is that program in C:

       /* Number of combinations of n things taken k at a time.
        * Use a recursive algorithm to calculate.
        */
       #include <stdio.h>

       void main()
       {  int N, K, C;
          printf("Enter values for N and K>>>");
          scanf("%d %d", &N, &K);
          C = Comb(N, K);
          printf("C = Comb(%d, %d) is %d\n", N, K, C);
          return;
       }

       int Comb(int N, int K)
       {
          printf("Call Comb with N and K =  %d %d\n", N, K);
          if (N == K || K == 0)
              return 1;
          else return Comb(N-1, K) + Comb(N-1, K-1);
       }

Along with sample output:

       Enter values for N and K>>>5
       2
       Call Comb with N and K =  5 2
       Call Comb with N and K =  4 2
       Call Comb with N and K =  3 2
       Call Comb with N and K =  2 2
       Call Comb with N and K =  2 1
       Call Comb with N and K =  1 1
       Call Comb with N and K =  1 0
       Call Comb with N and K =  3 1
       Call Comb with N and K =  2 1
       Call Comb with N and K =  1 1
       Call Comb with N and K =  1 0
       Call Comb with N and K =  2 0
       Call Comb with N and K =  4 1
       Call Comb with N and K =  3 1
       Call Comb with N and K =  2 1
       Call Comb with N and K =  1 1
       Call Comb with N and K =  1 0
       Call Comb with N and K =  2 0
       Call Comb with N and K =  3 0
       C = Comb(5, 2) is 10

For those doing Writebase (SSN, last 2 digits: 67-99), here is that program in C:

      #include <stdio.h>
      void writebase(int, int);
      char *D[] =
        {"0","1","2","3","4","5","6","7","8","9","a","b","c","d","e","f"};

      void main()
      {  
         int N, B;
         printf("Enter N and B:");
         scanf("%d %d", &N, &B);
         writebase(N, B);
         printf("\n");
      }

      void writebase(int N, int B)
      {
         printf("Call Base with N and B = %d %d\n", N, B);
         if (N != 0) {
            writebase(N/B, B);
            printf("%s", D[N%B]);
         }
      }

Along with sample output:

      Enter values for N and B:54790143
      16
      The values of N and B are: 54790143 16
      Call Base with N and B = 54790143 16
      Call Base with N and B = 3424383 16
      Call Base with N and B = 214023 16
      Call Base with N and B = 13376 16
      Call Base with N and B = 836 16
      Call Base with N and B = 52 16
      Call Base with N and B = 3 16
      Call Base with N and B = 0 16
      34407ff

In implementing each of these programs in MIPS, you should use the standard input parameters $a0, $a1 (for Comb and writebase) and also $a2, $a3 (for Hanoi), as well as $v0 for the returned value of Comb. Because these are recursive calls, you must save and store registers on the stack. In particular, after you have made a recursive call, if you have changed some $ai for the call, then you need to load it again from the stack if you want to use it again.
One tricky part of Comb is to realize that you cannot use $v0 for both returned values, but only for the second one (in the case where you call Comb twice). The value returned from the first call must be saved somewhere else (where?).
A tricky part of writebase is how to handle the strings "0", "1", ..., "f". I will talk about this in class.
For writebase you will need to use the div instruction, with quotient in the special register lo and remainder in hi. These registers must be accessed using the mfhi and the mflo instructions. (It would be possible to use pseudo-instructions, but then you would harder to get the remainder.)
You can simply select and copy the C code for your program above, and then compile and run it to see what the output should look like.

For checkoff:

Include your SSN in the program, to show that you are doing the correct one.
You must demonstrate your program in action using an input provided at the time of checkoff.
Hand the laboratory TA a copy of your source code when you start the check off procedure.

Revision Date: 2/19/99