Lab 9: MORE More more ... recursion Recursion RECURSION

This assignment has two parts. The first part is very similar to Lab 8, except that instead of computing the factorial of a number, you will compute the n-th Fibonacci number recursively. You will first implement your code in C, then in assembly. The second part is an example of recursion from a children's bedtime story! You are to implement this example in C only (assembly not required).

Your assignment must be submitted electronically by 11:59pm on Wednesday, November 4.

Exercise 1: Computing Fibonacci numbers

In this exercise, you are to write a recursive implementation of a function fibonacci() that computes the N-th Fibonacci number, i.e., Fibonacci(N), using the following definition:

Fibonacci(0) = 0, Fibonacci(1) = 1
Fibonacci(N) = Fibonacci(N-1) + Fibonacci (N-2)

This function takes in a single integer and will return an integer result. You can assume that the function will be called only with an argument small enough so that the result does not overflow, i.e., fits within 32 bits. A non-recursive implementation of the function will receive zero credit.

First implement this function in C. Your program should do the following:

The function must have the following name and type: int fibonacci(int n)
Write a main() procedure that repeatedly reads an integer from the input. Unlike the last assignment, your code does not have to parse a string into an integer; simply read the integer directly using scanf("%d", ...).
Then, main() calls fibonacci to compute the Fibonacci of this number.
Finally, main() uses printf("%d\n",...) to print the result.
These steps are repeated until a 0 value is read by main, its Fibonacci (=0) computed and printed, and then the program terminates.

Name the file with your C code ex1.c. Test it using your own inputs, and also the sample inputs provided.

Once your C code is working correctly, write the equivalent MIPS assembly program (ex1_main.asm and ex1_fib.asm), that does the same. That is, your main procedure must repeatedly read an integer from the input (using syscall 5, then call fibonacci to compute the Fibonacci number, and finally use syscall 1 to print the result. The program should terminate when the integer read is 0, but after computing and printing its Fibonacci value (=0).

Tip: Convert your C program one line-by-line to its assembly equivalent. Doing it any other way will take you much longer.
You must follow all of the procedure calling conventions discussed in class. Specifically, arguments must be passed to fibonacci in register $a0, and results should be returned in register $v0.
You have a lot of leeway in choosing the registers used by your procedures but you must follow the caller/callee save-restore conventions for these registers. Even if your code works, you will lose points if you do not follow the calling conventions.
The registers $ra, $fp, and any temporary ($t0-$t9) and saved registers ($s0-$s7) must be saved/restored according to conventions exactly as discussed in class.

Splitting up assembly code into separate files

Your assembly code must be split into separate files: one file for the main procedure, and a separate file for each of the other procedures (in this case, a separate file for fibonacci). Please use the templates provided on the class website. In particular, the file with the main procedure must start with:

        .data 0x0     # followed by global variables

        .text 0x3000
        .globl main

And the file with the fibonacci procedure must not have .data or .text declarations; instead it must start simply with:

        .globl fibonacci

Name the file with your main procedure ex1_main.asm, and a separate file with your fibonacci procedure ex1_fib.asm. Change the setting in MARS to allow compilations of multiple files (Settings --> Assemble all files in directory). Make sure that the file with the main procedure is open in the Mars editor; then press the assemble button.

Test the program using your own inputs, and also the sample inputs provided.

Exercise 2: A child couldn't sleep...

In this exercise, you are to write a recursive implementation of a function bedtimestory() that takes a sequence of words and spins them into a story, as follows. If the input to the function bedtimestory() is this sequence of strings—"child", "frog", "bear", "weasel"—then it prints the following output:

A child couldn't sleep, so her mother told a story about a little frog,
  who couldn't sleep, so the frog's mother told a story about a little bear,
    who couldn't sleep, so the bear's mother told a story about a little weasel,
      ... who fell asleep.
    ... and then the little bear fell asleep;
  ... and then the little frog fell asleep;
... and then the child fell asleep.

Note carefully the subtle differences in the outputs for the different strings above, especially the first and the last strings:

The output line for the first string ("child" in this example) is different from the remaining strings. The first line has "her mother" instead of "the child's mother". The last line has "the child" instead of "the little child". Also note the last line ends with a period instead of a semicolon.
The output for the last string ("weasel" in this example) is different from the remaining strings ("... who fell asleep.").
The indentation level is different for each line. Each extra indent is exactly two spaces.

The number of strings that bedtimestory() will be called with will be determined at runtime, not to exceed 20. You will write a main() procedure that will read these strings from the input, put them into an array of strings (up to 20 strings in the array, each string no longer than 15 characters including NULL), and pass this array to bedtimestory(). Use the following code template:


void bedtimestory(char words[20][15], int current, int number) {
  ...                   // Print something before
  ...                   // Recursive call to bedtimestory()
  ...                   // Print something after
}

main() {
  char names[20][15];   // Up to 20 names, each up to 15 letters long (incl. NULL)
  int num;

  ...                   // Read the names from the input
                        // until you read "END"

  bedtimestory(names, 0, num);
}

The main() procedure should read the strings from the input, each string on a line by itself. The last line of the input will have the string "END" on it, indicating that there are no more strings to be read. Use a loop with fgets() in main() to read the input, and store the strings in the array names, and keep track of the total number read. Then call bedtimestory().

For the above example, the input given to the program is:

child
frog
bear
weasel
END

Your implementation of bedtimestory() must be recursive. A non-recursive implementation of the function will receive zero credit. Moreover, since this is an exercise in generating text, any mismatches, including white space errors, will be penalized (except for the extra newline at the end of the output that is generated by MARS). Name the file with your C code ex2.c. Test it using your own inputs, and also the sample inputs provided. You are not required to do this part in assembly language!

Test Inputs, Due Date and Submission Procedure

Sample inputs and corresponding outputs are provided under /home/montek/comp411/samples/lab9. You should try running your program on the sample input files provided, and make sure the program's output is identical to that in the sample output files.

Your assignment must be submitted electronically by 11:59pm on Wednesday, November 4.

First copy the files ex1.c, ex1_main.asm, ex1_fib.asm and ex2.c to the CS Dept server (classroom.cs.unc.edu) under the appropriate folder in your home directory (e.g., comp411lab/lab9). Then, run the submit script:

% cd ~/comp411lab/lab9
% /home/montek/comp411/bin/submitlab9

In case of any problems, please contact the instructor or the TAs.

30 October 2015, Montek Singh, montek@cs.unc.edu