There are three problems in this homework, all designed to get us used to recursion and thinking recursively. For each problem, submit all the source files into a dropbox in ICON named Homework4.

Problem 1

We want to write a java method boolean search(int [] arr, int x) that checks if x is present in the array arr that we assume is sorted in non-decreasing order. We want to do this, as shown here, by invoking the recursive binary search method recSearch. Complete the latter method by filling in the missing pieces.

Problem 2

We want to write a java method reverseArr(int [] arr) that reverses the order of the elements in arr. We want to do this, as shown here, by invoking the recursive method void reverseArray(int [] A, int i, int j) that takes an input an integer array A, indices i and j and reverses the order of the subarray A[i..j]. Fill in the code for this latter method (which is discussed in Section 3.5 of the text.)

Problem 3

We want to add an instance method public boolean search(String s) to the SLinkedList class here. This method should return true or false depending on whether s is present in the linked list. The method works by calling the recursive method private boolean recSearch(String s, Node n), and your task is to complete that method by filling in what's missing.