Java Object Oriented Programming II - Computing Powers with Recursive Methods

Computing Powers This problem is a case study in using recursive thinking to improve the efficiency of an iterative algorithm. You will write a sequence of methods for the exponentiation of floating point numbers. Parts I and II involve writing rather simple-minded iterative and recursive methods for the task. In Parts III and IV you use more sophisticated recurrence relations in order to write more efficient recursive methods. In Part V you convert your method from Part IV into an iterative method that is far more efficient than the Part I iterative method. You may put all of your code for this project into a single class file - PowersUsername.java. All of your methods should be static Part I Write an iterative method called powerl to compute b, where b is of type double and n is an integer20 Use a simple for-loop that repeatedly (n times) multiplies an accumulator variable byb Part II Write a recursive method power2 that accomplishes the same task as powerl, but is based on the following recurrence relation Part III Write a recursive method power3 that is identical to power2 except that it is based on this recurrence relation b0- 1 bn (bn/2)2 bn-b (bn/2)2 ifn> 0 and n is odd (Note: This equation is not true in math. Why is it true in Java?) if n>0 and n is even Note: If n is a large exponent, then power3 should perform far fewer multiplications than power2. In particular, when computing something like (b2, there is no need to compute b2 twice. Rather, compute it once, store it in a variable, and then compute the result of multiplying the variable by itself. Part IV Write a tail recursive helper method called multPow, that computes the value of a b. Base your implementation on the following recurrence relation: a*bn-a*(b2)n/2 if n>0 and n is even if n>0 and n is odd Then write a method called power4 that computes b simply by making the call multPow(, b, n). Note that in this approach, the extra parameter a used by the helper method is serving as an accumulator for the result