# Recursive Powers Exercise

## 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're done, email the code to ifinlay@umw.edu.

Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.