Question 1: Rewrite the getReferenceTo method in the LinkedBag class using recur
ID: 3724318 • Letter: Q
Question
Question 1:
Rewrite the getReferenceTo method in the LinkedBag class using recursion.
For full credit, do not invoke the toArray method.
The original, non-recursive version is below.
private Node getReferenceTo(T anEntry) {
boolean found = false;
Node currentNode = firstNode;
while (!found && (currentNode != null)) {
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
}
return currentNode;
}
Question 2:
Write a recursive method from the client perspective that returns the sum of integers contained in a list.
The method header is: public static int sumList(ListInterface<Integer> list)
The list should not be altered when the method ends.
Do not invoke the toArray method.
Question 3:
Write a recursive method that counts the number of positive integers in a bag from the client perspective.
The bag should not be changed as a result of the method call.
The method header is: public static int countPositives(BagInterface<Integer> bag)
Do not create a duplicate copy of the bag.
Do not invoke the toArray method!
Hint: think about how you can add code both before and after the recursive call!
Driver program:
import java.util.*;
public class HomeworkW07Driver {
public static void main(String[] args) {
// Note: you need to use a revised ArrayBag and LinkedBag
classes to test these methods
// Q3
ArrayBag<Integer> numbersArrayBag = new
ArrayBag<Integer>();
numbersArrayBag.add(1);
numbersArrayBag.add(2);
numbersArrayBag.add(1);
numbersArrayBag.add(4);
numbersArrayBag.add(3);
System.out.println("The bag contains[1, 2, 1, 4, 3]
" + Arrays.toString(numbersArrayBag.toArray()));
System.out.println("Should be 2: " +
numbersArrayBag.getFrequencyOf(1));
System.out.println("Should be 1: " +
numbersArrayBag.getFrequencyOf(4));
System.out.println("Should be 0: " +
numbersArrayBag.getFrequencyOf(5));
// Q4
LinkedBag<Integer> numbersLinkedBag = new
LinkedBag<Integer>();
numbersLinkedBag.add(1);
numbersLinkedBag.add(2);
numbersLinkedBag.add(1);
numbersLinkedBag.add(4);
numbersLinkedBag.add(3);
System.out.println("The bag contains[3, 4, 1, 2, 1]
" + Arrays.toString(numbersLinkedBag.toArray()));
System.out.println("Should be 2: " +
numbersLinkedBag.getFrequencyOf(1));
System.out.println("Should be 1: " +
numbersLinkedBag.getFrequencyOf(4));
System.out.println("Should be 0: " +
numbersLinkedBag.getFrequencyOf(5));
// Q5
// this is a private method- so you'll have to test it
internally!
// Q6- try it with both AList and LList!
ListInterface<Integer> numbersList = new
AList<Integer>(); // swap this out for an LList- your code should still
work!
numbersList.add(4);
numbersList.add(1);
numbersList.add(3);
numbersList.add(2);
numbersList.add(0);
numbersList.add(9);
System.out.println("Sum is 19: " + sumList(numbersList));
//Extra Credit- try it with both ArrayBag and LinkedBag!
BagInterface<Integer> numbersBag = new
ArrayBag<Integer>(); // swap this out for LinekdBag- your code should
still work!
numbersBag.add(2);
numbersBag.add(-1);
numbersBag.add(3);
numbersBag.add(5);
numbersBag.add(-2);
numbersBag.add(-4);
numbersBag.add(1);
System.out.println("The bag contains[2, -1, 3, 5, -2, -4,
1] " + Arrays.toString(numbersBag.toArray()));
System.out.println("There are 4 positives: " +
countPositives(numbersBag));
System.out.println("The bag still contains [2, -1, 3, 5,
-2, -4, 1] " + Arrays.toString(numbersBag.toArray()));
}
public static int sumList(ListInterface<Integer> list) {
return 0;
}
public static int countPositives(BagInterface<Integer> bag) {
return 0;
}
}
Explanation / Answer
Part 1:
private Node getReferenceTo(T anEntry, Node currentNode) {
if(currentNode == null){
return null;
}
else if(currentNode != null && anEntry.equals(currentNode.data)){
return currentNode;
}
else{
return getReferenceTo(anEntry,currentNode.next);
}
}
================================================================
Part 2:
public static int sumList(List<Integer> list){
if(list.size() == 1){
return list.get(0); // End recursion on last element in list
}
else {
return list.get(0) + sumList(list.subList(1,list.size()-1)); // Recursively call sumlist on sublist of initial list
}
}
=============================================================================
Part 3:
public static int countPositives(BagInterface<Integer> bag){
BagInterface<Integer> bg = bag.clone(); // Create a copy of the current bag
if(bg.size() == 0){ // If bagis empty
return 0;
}
else if(bg[0] > 0){
int count = bg.getCount(bg[0]); // count number of occurence of same number
bg.remove(bg[0], count); // Remove it from the bag
bg.trimToSize(); // Trim bag size
return count + countPositives(bg); // Add the count to the result
}else{
int count = bg.getCount(bg[0]);
bg.remove(bg[0], count);
bg.trimToSize();
return countPositives(bg);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.