Computer Science Department
Johns Hopkins University
600.333/433
Computer Systems Fundamentals
Fall 2002
(Last updated:Tuesday, 15-Oct-2002 17:47:19 EDT)

Programming project 2:
Designing low level recursion

Due date Friday December 6, 2002
(By midnight)

1. Objective

Understand how to use recursion to define concepts.
Learn to implement a recursive function using low level instructions.

2. General Instructions

For this project you are required to implement several programs under the MIPS programming language, and test them by using the RISC simulator SPIM. There are several questions about your programs you must answer and send them along with the programs.

Submit your programs by midnight of the due date to the CSF address, cs333@cs.jhu.edu. Please put all the programs in the same message as several different attachments. Also, type the answers to the questions on this labwithin the same e-mail where your programs are.

If you need a guide to start working with SPIM, read the document Working with SPIM , available at http://www.cs.jhu.edu/~cs333/#weblinks.

For a complete reference on the MIPS programming language use the textbook Computer Organization and Design, 2nd ed. , by Hennessy and Patterson, chapter 3 and appendix A.

IMPORTANT: In all your submissions, please state clearly your name, major, e-mail and level (333 or 433). Also, thoroughly comment your code.
NOTE: The postmark in your e-mail message will indicate the time you submitted the programs, and at most it shall be 11:59 PM on the due date. .
REMEMBER: The concepts involved in this lab may be matter for exams.

3. Programming Activities

Hand trace the following recursive function and identify its purpose, then implement it. The program must work correctly for any integer between -50 and +50.
```
         
         fun (n)
            if n = 0 then return 0
            else if n < 1 then return fun (-1*n)
            else return 1+fun(n-1)
         end fun
```
The value n must be read from the keyboard and your program must display the resulting number.

Questions
1. What would be an appropriate name for the function?
2. What is the maximum value n that can be handled without producing a stack overflow? (Hint: Try numbers beyond the range above stated.)
3. Describe the way you pass one parameter to a function.
4. Show implementions of stack operations push and pop.
5. Is there any significant difference between growing the stack up or down? (Hint: Sketch a drawing of the computer memory, and follow the function.)
6. What happens if your program for fun does not test the base case for n = 0?
Implement the following recursive Fibonacci function [Hennessy's textbook, p.205, problem 3.27]. Note that n must be greater than or equal to 0. Your program must work correctly for any integer less than 21. Notice that the first call must be fib (1,0,n).
```
    
         fib (a,b,n) 
            if n = 0 then return b
            else return fib (a+b,a,n-1)
         end fib      
```
The value n must be read from the keyboard and your program must produce the nth Fibonacci number.
Questions
1. Describe the way you are passing the 3 parameters, a, b, and n to the Fibonacci function.
2. Why is the base case tested before any other operation?
3. What is the difference between your assembly language program for the Fibonacci function shown above with respect to the program for the original Fibonacci function shown below: [Hennessy's textbook, p.205, problem 3.26].
```
   
        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
       
```
4. Write the MIPS program corresponding to the previous function (you don't have to test it.)

4. Iteration and recursion (only for 433 students)

Use the fun recursive function for a positive parameter m to create a program that iteratively produces and prints a series of numbers between and including -m and +m, i.e., your program must produce and print:
fun(-m), fun (-m+1), ..., fun(-1), fun(0), fun(1), ..., fun(m-1), fun(m)
Questions
1. Did you have to modify the original recursive fun function to generate this sequence?
2. Explain your method for generating the sequence.
The power of a positive number is typically computed using an iterative operation. Modify this computation to be recursive and implement it.
The values n and m for m^n must be read from the keyboard and your program must produce m^n by calling the recursive function. (Note: m^n means m is multiplied by itself n times.)
1. What is the recursion and associated base case for computing the power of a positive number (that is, when no iteration is utilized)?
2. What are the similarities for your program for computing the power of a positive number with respect to your recursive program fun?

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

Return to the CSF Homepage