1 short recursion practice a a prime number is an integer that cannot be divided by 5346819
(1) Short Recursion Practice
a) A prime number is an integer that cannot be divided by anyinteger other than one and itself. For
example, 7 is prime because its only divisors are 1 and 7. Theinteger 8 is not a prime number because it
is divisible by 1, 2, 4, and 8. In a class called RecursionTester,write a recursive static method called
isPrime(int x) that returns a boolean with the value true if andonly if the given integer x is a prime
number. Assume that x is positive. The method should have no loopsof any kind. You may use
indirect recursion … the following definitions should help giveyou some ideas:
isPrime(1) = true
isPrime(N) = isPrime(N, N-1)
isPrime(N, 1) = true
isPrime(N, X) = false if X divides N evenly, otherwise isPrime(N,X-1)
b) Write a method in the RecursionTester class called sort(int[] v)which takes an integer array and
sorts the array in increasing order. Note that the method shouldsort the array given, not create any new
arrays. Also, you MUST write the method recursively to get anymarks. You will want to use a helper
method. (Hint: Move left to right through the array recursively,swapping a pair of elements if the one on the left is larger
than the one on the right. Use a parameter to keep track of theposition of the element pair that you are examining. If you
reach the end of the array and no items have been swapped, then thearray is sorted now and you can stop. Otherwise, you
will need to restart the swapping process from the beginning of thearray. You'll need to keep track of whether or not you
made a swap…use another parameter). It may be helpful to write amethod that will display your array, so that
you can use this for debugging. Here is an example of how to testit from a main method, assuming that
you have a method called displayArray to display the array:
int[] v = {3, 6, 9, 2, 7, 1, 5, 8, 4, 2, 2, 1};
sort(v);
displayArray(v);
Make sure to hand in your testing for both of these methods. Tryvarious test cases.
(2) The MAZE GUI
Create a class called Maze that represents a maze in which a robotcan move up, down, left or right in
(i.e., a grid that allows only horizontal and vertical movements).A maze can have walls or open
areas. A robot cannot pass through the walls but may move freelythrough the open areas. Each grid
location is identified by a row and a column number (starting at0,0) and may store “something” to
indicate whether a wall is in that location. Here is an example ofa 10×10 maze:
Get the 4 text files labeled maze1.txt, maze2.txt, maze3.txt andmaze4.txt from the course website that
represent the following mazes:
Create a GUI in a class called MazeSolver that displays the mazes.Here are the GUI expectations:
• The GUI must show the maze walls and open areas clearly,although upon startup, the maze may
be in any kind of reasonable “empty” configuration.
• The GUI should allow you to load one of the 4 maze files byusing the JFileChooser from the
javax.swing package.
• Upon choosing a file, the maze should be displayed rightaway.
• The user should be able to select a start location bypressing the left mouse button on an open
maze location and a end location by pressing the right mouse buttonon an open maze location.
If a start or end location was already selected, they are replacedby the new selected locations.
These locations should be shown visually somehow. A user may NOTselect a wall as a start or
end location.
• The GUI should have a PATH EXISTS button and a FIND PATHbutton. These will call methods
that you will write in the next part of the assignment.
• Clicking on the X at the top right of the window shouldcause the application to quit and the
window to close.
(3) The MAZE Recursion
Create the following recursive instance method in the mazeclass:
public boolean pathExists(Point start, Point end) { … }
This method should determine whether or not there is a path in themaze between the start and end
locations. There is a path if there is a consecutive sequence ofadjacent non-wall grid locations. Try to
come up with a recursive definition along the notion of: “if thereis a path to the destination from one of
the other non-wall grid cells beside the start location, then theremust be a path to the start location as
well”. You MUST NOT use any FOR loops or WHILE loops to solve thisproblem, otherwise you'll lose
all your marks here. However, you are allowed to initialize themaze to some values before you start
looking for a path…and in that case, you may use a for loop to”reset” all maze locations to some
particular value. Note that the Point class is in the java.awtpackage. Note that this method merely
returns whether or not a path exists, but it does not return apath.
Test your code by calling from the PATH EXISTS button on your GUI,which makes use of the selected
start and end locations. If a start or end location has not beenchosen, an appropriate JOptionPane
should be shown instead of calling the method. The result should bedisplayed in a JOptionPane with
appropriate and clear text output.
Now using recursion again, write another method called:
public ArrayList pathFrom(Point start, Point end) { … }
This method should now return the path as an ArrayList ofcoordinates (use Point class in java.awt
package). Note that you may use helper methods and you can usedirect or indirect recursion. Once
again, this method should not have any FOR or WHILE loops, but youmay reset the maze with
FOR/WHILE loops before this method is called.
Test your code by calling from the FIND PATH button on your GUI,which makes use of the selected
start and end locations. If a start or end location has not beenchosen, an appropriate JOptionPane
should be shown instead of calling the method. The result should bedisplayed on the maze itself,
showing the points from the resulting ArrayList by somehowdisplaying the corresponding locations on
the maze window.
**** you may require this****
maze1
1111111111
1000110001
1010100101
1010001101
1000011001
1110001101
1001000101
1011110111
1000000001
1111111111
maze2
1111111111
1000000001
1011111101
1010000101
1010110101
1010111101
1010000001
1011111111
1000000001
maze3
1111111111
1000110001
1010011101
1001001001
1101101011
1001001001
1011011101
1001001001
1101101011
1111111111
maze4
1111111111
1000000001
1011111101
1010000101
1010000101
1010000101
1010000101
1011111101
1000000001
1111111111
1111111111