Programming lab 3:
Iterative and Recursive Procedures

(Due on Monday October 19 Thursday October 22, 2009 by midnight.)

1. Objectives

• Learn to implement procedures and to pass parameters.
• Understand how to use recursion to define concepts.
• Learn to implement recursive functions and handle a stack using low level instructions.

2. General Instructions

For this lab you are required to implement several programs using the MIPS programming language and test them with the simulator SPIM. There are several questions you must answer and submit along with your programs.

Your assignment has to be submitted electronically by midnight (i.e., 11:59 PM) on the due date.

Additional resources:

• Brief guide to start working with SPIM ( http://www.cs.jhu.edu/~jorgev/cs333/spim_man.html.)
• MIPS reference with examples ( http://www.cs.jhu.edu/~jorgev/cs333/reference.html.)
• For a complete reference on the MIPS programming language use the textbook Computer Organization and Design, 3rd ed., by Hennessy and Patterson, chapter 2 and appendix A.

3. Programming Activities

A. Procedural subroutines
1. Read a character string from the keyboard and indicate how many characters it contains.

   Notes

   • The characters should be read from the keyboard all at once, not one by one.
   • Your program should have at least three subroutines:
     1. Read string
     2. Count characters
     3. Print count
   • The count characters procedure must receive the beginning of the string as parameter.
   • The print procedure must receive character count as parameter.
   • No procedure can use information from the rest of the program, only what is being provided as parameter.
   • Describe your technique within a comment inside the code.
   • Hint: Be careful with memory allocation.

2. Only for 433 students: Using the techniques developed in the previous activity, design a program that reads a binary string (i.e., 10011101) from the keyboard and returns its equivalent decimal value.

   Notes

   • The length of the binary string the user inputs must be between 1 and 10 bits.
   • All inputs should be regarded as positive integers.
   • The binary digits should be read from the keyboard all at once, not one by one.
   • Your program should have similar constrains and requiremenst as the one in the previous activity.
   • Hint: It's not as hard as it seems.

   
   

   B. Recursive subroutines

3. Read a decimal number from the keyboard (a value between 0 and 1023) and print its binary equivalent.

   Notes

   • The decimal to binary conversion must be performed in recursive way.
   • Describe your technique within a comment inside the code.
   • Hint: Be careful with memory allocation.

4. Watch the video Assignment Discovery: Fibonacci Sequence

   Questions:

   1. How many rabbits do you have the first month?
   2. How many rabbits do you have the fourth month?
   3. How many rabbits do you have the sixth month?
   4. What procedure is followed to predict the amount of rabbits at any given month?
   
   

5. Implement a recursive function to compute Fibonacci numbers.

   Notes

   • The textbook provides the following function to compute recursively the number of rabbits at the n^th month.

      
             fib (n)
                 if n = 0 then return 0
                 else if n = 1 then return 1
                 else return fib(n-1) + fib(n-2)
              end fib
     

   • Your procedure must be named fib and should produce the n^th Fibonacci number. It does not track how the population is growing.
   • Regard 1 as the first number in the sequence (we don't get rabbits out of the blue.)
   • The value n must be passed through register $a0. Result must be returned through register $v0.
   • The procedure must work correctly for any integer lesser than 21. To this end, manually make a table with all the Fibonacci numbers between n = 1 and n = 20, and compare against the computer results. (Include both tables in your submission.)
   • You may use the skeleton provided at the end of this page.
   • See what is the largest number your program can compute, describe what happens and try to guess why.

   Questions:

   1. What value does fib return when $a0 is 6?
   2. How many times fib is called when $a0 is 6?
   3. What is the content of register $sp right before fib is called for the 1^st time?
   4. What is the content of register $sp right before fib is called for the 5^th time?
   5. What is the difference between the instructions j, jr, and jal?
   6. What happens if the procedure does not test the base case?
   7. Describe how to implement the operations push and pop.

6. Only for 433 students: Modify the previous program to take advantage of a technique called tail recursion.

   Notes

   • The textbook also provides another recursive function to compute Fibonacci numbers.

      
              fib (a,b,n) 
                 if n = 0 then return b
                 else return fib (a+b,a,n-1)
              end fib  
     

   • Your procedure must be named fib2 and should produce the n^th Fibonacci number. It does not track how the population is growing.
   • Regard 1 as the first number in the sequence (we don't get rabbits out of the blue.)
   • The values n, a and b must be passed through registers $a0, $a1 and $a2, respectively. Result must be returned through register $v0.
   • The procedure must work correctly for any integer lesser than 21. (Compare your results with the table created in the previous exercise.)
   • You may use the skeleton provided at the end of this page.
   • See what is the largest number your program can compute, describe what happens and try to guess why.

   Questions:

   1. What should be the values for a,b and n so the function returns the same number as the amount of bunnies at the end of the movie?
   2. What value does fib2 return when $a0 is 6?
   3. How many times fib2 is called when $a0 is 6?
   4. What is the content of register $sp right before fib2 is called for the 1^st time?
   5. What is the content of register $sp right before fib2 is called for the 5^th time?
   6. What is the difference between fib and fib2?
   7. Explain why the base case is tested before performing any other operation?
   8. How different is a recursive implementation that grows the stack up from one that grows the stack down?
   9. How do you prevent 0 from being the first number produced?

7. Extra credit: Modify any of your previous Fibonacci program to display how the population of rabbits grows in time.
   
   

   C. Skeleton

   # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 
   # 
   #     Computer Systems Fundamentals 600.333/433. Fall 2009
   #              Project #3: Fibonacci Function.
   # 
   # Description:  Compute the fibonacci function using a recursive
   #               process.
   # Function:     F(n) = 0,        if n = 0;
   #                      1,        if n = 1;
   #                      F(n-1) + F(n-2), otherwise.
   # Input:        n, (0<=n<21) 
   # Output:       F(n).
   # Instructions: Load and run the program in SPIM, and answer the prompt.
   # Algorithm for main program:
   #       prompt for input n
   #       call F(n) 
   #       print result.
   # Register usage:
   #  $a0 = n (passed directly to fib)
   #  $s1 = F(n)
                   .data
                   .align 2
   # Data for prompts and output description            
   prompt1:        .asciiz "\n\nThis program computes the Fibonacci function"
   
   prompt2:        .asciiz "\nEnter value for n:"
   descr:          .asciiz "fib(n) = "
   prompt3:        .asciiz "\n"
                   .text
                   .align 2
                   .globl main
   
   main:
   # Print the prompts
                   li $v0, 4       # print_str system service
                   la $a0, prompt1 # ...passing address of first prompt
                   syscall
                   li $v0, 4       # print_str system service...
                   la $a0, prompt2 # ...passing address of 2nd prompt
                   syscall
   # Read n and call fib with result
                   li $v0, 5       # read_int system service
                   syscall
                   move $a0, $v0   # $a0 = n = result of read
                   jal fib         # call F(n)
                   move $s0, $v0   # $s0 = F(n)         
   # Print result
                   li $v0, 4       # print_str system service...
                   la $a0, descr   # ...passing address of output descriptor
                   syscall
                   li $v0, 1       # print_int
                   move $a0, $s0   # ...passing argument fib(n)
                   syscall
   		la $a0, prompt3
   		li $v0, 4
   		syscall
   
   # Call system -exit
                   li $v0, 10
                   syscall            
   
   # --------------------------------------------------
   # ---- Insert your Fibonacci function here 
   
   

   ---

   Any concerns about the goals, questions, or wording of this document, please send a message to Jorge Vasconcelos.

   ---

   Return to the CSF Lab homepage