In this lab, you will be creating many recursive functions to work with the tree data structure. In this first section of the warmup, you will work with a partner on several recursive functions to refresh your memory of how recursion works.
To start, open the Recursion.java and LinkedNode.java files provided to you. We have given you some functions to fill in, as well as some test code in the main method that you can uncomment when you are ready to use it.
We will start with a method that recursively reverses a String. This is the public static String rev(String s) method in Recursion.java. Calling it with the argument “CS 151 is fun!” should return “!nuf si 151 SC”. To help design your solution, you may want to look into the String substring methods, which you can find documentation for at https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/lang/String.html.
The second method we will write calculates the sum of the integers in a singly linked list. This is the public int sum() method in LinkedNode.java. The LinkedNode class stores (1) an integer in its item instance variable and (2) a pointer to the next node in the next instance variable. The tail of the linked list is indicated by a null value in the next instance variable. If you call this method on the list of numbers [1, 2, 3, 4], it should return the value 10.
The third method we will write calculates the sum of the integers in an array list. This is the public static int sum(ArrayList<Integer> numbers) method in Recursion.java. This method should remove every value from an array list of integers and return their sum. Like the previous method, if you call this method on an array list of numbers [1, 2, 3, 4], it should return the value 10, but this time the list of numbers would be empty after you ran it.
For our fourth and final recursive function, we will write a method that prints an array list of numbers on separate lines and adds a tab indentation after each even number. This is the public static void printIndent(ArrayList<Integer> numbers) method. Our method will once again remove every integer from the list. So if we ran this on an array list of numbers [1, 1, 2, 3, 5, 8, 13], it should print:
1
1
2
3
5
8
13
To complete this method, it is probably easier to write a recursive helper method that takes in the ArrayList and a String prefix to print before the next number. Then, the printIndent method does not need to be recursive but can instead simply call the helper method with the array list and an empty initial prefix.
Don’t forget to frequently save your progress to GitHub using the add, commit, and push commands with git.