Objective: Implement some recursive algorithms $--$ most related to sorting.

all methods you define should be marked static.

Q$0($warmup$)$: reversing a generic list recursively

Write a recursive method named rev that is parameterized by a generic type A$.$

The method should take a List as a formal parameter and return a List that's the same as the input list, but with everything in reverse order.

Some examples $($using $[..]$ as an abbreviation for List.of$(...))--$ put these in the main and print the results:

rev$([\text{'}$c$\text{'},\text{'}$o$\text{'},\text{'}$t$\text{'}])$; $//$ returns $[$t$,$ o$,$ c$]$ rev$($new ArrayList$<>())//$ returns $[]$

Try to do this one without a helper method...

Note: since you'll need to mutate the input list $($which in many cases will be read$-$only$/$immutable$),$ you will need a "kick$-$off" method to make a defensive $($mutable$)$ copy of the input list $--$ as it may get destroyed$/$mutated during reversal.

For example:

public static Foo exampleMethod$($List inputList$)\{$ return realExampleMethod$($new ArrayList$<>($inputList$))$; $\}$ private static Foo realExampleMethod$($List lst$)\{//$ recursive code in here $//($can now safely mutate lst$)\}$

The exampleMethod$(..)$ copies its input list and passes the mutable copy to the other method $($realExampleMethod$)--$ which does all the actual work.

Q$1$: merging two sorted lists recursively

A key 'helper' method used in merge sorting algorithm is the merge$(..)$ method.

The merge method should be parameterized by an orderable generic type U that extends Comparable.

the method should take as parameters two sorted, orderable$-$generic List: I'll call these lists xs and ys

the method should return a list of U

Here are some examples $($where $[]$ is used as pseudocode for List.of$(..))--$ print these in the main:

merge$([],[1,4,5])//$ returns $[1,4,5]$ merge$([1,3],[1,4,5])//$ returns $[1,1,3,4,5]$ merge$([1],[])//$ returns $[1]//$ returns $[$a$,$ b$,$ c$,$ d$,$ e$,$ f$,$ g$]$ merge$([\text{'}$b$\text{'},\text{'}$d$\text{'},\text{'}$e$\text{'},\text{'}$f$\text{'}],[\text{'}$a$\text{'},\text{'}$c$\text{'},\text{'}$g$\text{'}])//$ SHOULDN'T WORK: $//$ merge method contract violation $//($one of the input lists isn't sorted$)//$ merge$([],[4,3])//$ returns $??$

tester.java

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

public class Tester $\{$

$//$ todo: static rev$(..)$ method here

$//$ todo: static merge$(..)$ method here

public static void main$($String$[]$ args$)\{$

$//$ todo: sample calling code for q$0$ here

System.out.println$("----")$;

$//$ todo: sample calling code for q$1$ here