15-121 SPRING 2010 [CORTINA]

LAB 7

In this lab, you will implement several recursive methods.

EXERCISES

Download the project Lab7.zip. This project has three classes, one for each exercise below. Complete the required methods below.

  1. Write a recursive method sum for the SumComputer class that has one parameter, a positive integer n, and returns the sum of the positive integers from 1 to n. Your answer should not have a loop in it.

  2. Write a recursive method count for the LetterCounter class that has two parameters, a string and a character, and it returns the number of times the character appears in the string. You may only use the following String methods as necessary: charAt, substring, equals, length. Your answer should not have a loop in it.

  3. Write a recursive method printInReverse for the SinglyLinkedList class that prints the elements of this linked list in reverse order. Do not change the list. Your answer should not have a loop in it.

    HINT: You will need a wrapper method here as we discussed in class. To print the reversed list starting at some given node, print the rest of the list in reversed order and then print out the data in the given node.

  4. [HARDER] Write a recursive method makePermutations for the PermutationGenerator class that has a string as its parameter and returns an array list containing all strings that are permutations of this string. A permutation is a string that consists of all of the characters in the original string in some order. For example, the permutations of "ABC" are "ABC","ACB","BAC","BCA","CAB","CBA". You may only use the following String methods as necessary: charAt, substring, equals, length.

    HINT: For each character of the original string, remove the character and find all the permutations of the resulting substring. Concatenate each of these on to the removed character to form the permutations that start with the removed character.

    RUNTIME COMPLEXITY: If there are n characters in the original string, how many permutations are there as a function of n?

HANDIN

If you worked with another student, put both of your names in a comment at the beginning of your program. At the end of lab, create a zip file of your program and submit it to the handin server http://handin.intro.cs.cmu.edu/v1. (If you worked together, you only have to submit one program.)

FUTURE WORK: FUN STUFF FOR LATER