COS 126 Exercise Set 4

Answers

These programming exercises are intended help review the material on TOY programming and on recursion. Do not turn in solutions.

1. Here's another implementation of the Fibonacci numbers (from /u/cs126/examples/fib4.c):

   int fib(int n, int p) {
   	int n2;
   
   	if (n < 2)
   		return 1 + p;
   	n2 = fib(n-2, p);
   	return fib(n-1, n2);
   }

   fib(n,0) returns the nth Fibonacci number. Implement this version of fib in TOY machine language using the calling conventions for recursive functions described on pages 11-6 and 11-7 of lecture 11. See /u/cs126/toy/sum2.toy. Run your program with n = 20 (the answer should be 2AC2).
2. Revise your solution to the previous exercise to eliminate the tail recursion in your TOY program.
3. int itoa(int n, int b, char str[]) fills str with a null-terminated string giving the character representation of n in base b and returns the length of this string. For example:

   char buf[20];
   k = itoa(875, 5, buf);
   printf("%s\n", buf);

   Sets k to 5 and prints 12001. Implement itoa using recursion. You'll find it easiest to make itoa itself nonrecursive, and to have it call a recursive helper function that is a variant of convert. convert is described on page 10-4 of lecture 10 and is available in /u/cs126/examples/convert.c.
4. Write a completely nonrecursive version of itoa.

Answers

Try to implement these programs before looking at the suggested solutions.

1. fib2.toy
2. fib3.toy
3. itoa.c (recursive)
4. itoa1.c (nonrecursive)