Lab 9: More Recursion

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. Keep in mind the following:

• The function must have the following name and type: unsigned int fibonacci(unsigned int n)
• Points will be deducted if the return type of the function is not unsigned int.

Your program should do the following:

• 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("%u\n",...) to print the result. Note: The format string for printf uses "%u" instead of "%d" to indicate that an unsigned int is to printed.
• 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.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.
• Be sure to use the unsigned version of addition instructions. This way, the value of the largest Fibonacci that fits in a register is doubled! You will lose points if your entire calculation is not unsigned.
• You must follow all of the procedure calling conventions discussed in class. Specifically, arguments must be passed to a_to_i and factorial 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.
• You do not need to save/restore $fp and $gp because you will likely not be needing them. However, $ra, and any temporary registers ($t0-$t9) and saved registers ($s0-$s7) must be saved/restored according to conventions exactly as discussed in class.

Name the file with your assembly code ex1.asm. Test it 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 text 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 text 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. 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. 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!