Homework 8: Recursion In a single class, called Recursion, write each of the following 6 static methods. Also, include a main method in your class where you have at least two tests per method. Be sure to include a comment for each test that states the expected output and the actual output. Be sure to comment the rest of your code as well! 1. Write a recursive method, called reverseString that takes in a string and returns the reverse of the string. 2. You're standing at the base of a staircase and are heading to the top. A small stride will move up one stair, a large stride advances two. You want to count the number of ways to climb the entire staircase based on different combinations of large and small strides. For example, a staircase of three steps can be climbed in three different ways: via three small strides or one small stride followed by one large stride or one large followed by one small. A staircase of 5 steps can be climbed in eight different ways (I'll leave it up to you to enumerate each way :-1 Write a static recursive function int countWays(int numStairs) that takes a positive numStairs value and returns the number of different ways to climb a staircase of that height taking strides of one or two stairs at a time 3. Ackermann's function is a recursive mathematical algorithm that can be used to test how well a computer performs recursion (It is also important mathematically as well, as it is the first known function that is totally computable but not primitive recursive!). Write a method Ackermann(int m, int n), which solves Ackermann's function. The function is given by the following: ifm 0 If m > 0 and n = 0 n 1 A(m, n)A(m 1.1) A(m 1. A(m,n 1)) if m>0 and n>0 Note when testing this method keep m and n small, as A(4,2) is an integer of 19,729 digitis! 4. There are n people in a room, where n is an integer greater than 1. Each person shakes hands once with every other person. What is the total number, h (n), of handshakes? Write a recursive function, called handShakes(int n), to solve this problem. It should return an int for the total number of handshakes for n people 5. The following method was known to the ancient Greeks for computing square roots. Given a value x 0 and a guess g for the square root, a bett Write a recursive helper method squareRootGuess(double x, double g). If g2 is approximately equal to x (within.0001 ofx) return g, otherwise, keep going until you get a better guess. Then write a method squareRoot(double x) that uses the helper method. You cannot use Math.sqrt in solving this problem. Hint: if this method really works does it matter what the initial guess is