Lab 6: Recursive Powers

Objective

To practice writing recursive functions.

Task

For this lab, you will write a program to read in two integers from the user, $base$, and $exponent$, calculate the value of $base^{exponent}$ and print this value to the screen. To do this, you will write two recursive functions:

The first will get a positive number from the user. If the user enters a number less than or equal to 0, it should keep recursing until the number is positive. You would normally do this with a loop, but use recursion instead.
The second will compute the power using the following recursive formula:

\[ X^Y = \begin{cases} X^{(Y/2)} \cdot X^{(Y/2)}, \hfill & \text{ if $Y$ is even} \\ X^{(Y/2)} \cdot X^{(Y/2)} \cdot X, \hfill & \text{ if $Y$ is odd} \\ \end{cases} \]

You will have to add a base case to the function so that it will eventually bottom out and return a value directly. Think about what the base case for exponentiation is.

This method of computing powers is actually more efficient than the straightforward loop solution of looping $exponent$ times and multiplying $base$ that many times! Sometimes the more efficient algorithm is most naturally expressed with recursion.

Remember, this program can only use recursion, it should have no loops at at all!

The main function should simply call the function to get input two times, then pass those values to the power function, printing the output.

Example Run

Below is an example run of this program:

$ java Powers
Enter a positive number: 0
I said a positive number!
Enter a positive number: 3
Enter a positive number: -4
I said a positive number!
Enter a positive number: 4
81

Submitting

When you are finished, please upload your code to the Canvas page for this assignment.