V22.102:Honors Data Structures
Spring 2000
Assignment I

Some simple exercises with recursion.
Due: Monday January. 31

a) Test the code for factorial and for permutations given in the text, and
verify that they work. Test permutations with an array of short strings.

b) Write a Java routine to compute the Fibonnaci numbers, defined recursively
as follows:
                        F (0) = 1
                        F (1) = 1
                        F (n) = F (n-1) + F (n-2) for n > 1

c) Modify your program in b) to count how many times the routine F is called
for a given value of its argument. Your test program should have a loop that
displays the following output:

                     Value of n   Value of F(n)     number of calls to F
                        ...           ...                 ....

Please send the sources and output of your program to me and to the grader,
as a regular ascii file.