Write a program using recursion that finds the value of numbers raised to a power. Learn more about new approaches that can be used to find the result of raising numbers by a N-power.
- [Instructor] I'm sure you're familiar with using the Java API the math class to be able to find the value of a number raised to a power. We would use math dot POW. Inside the parentheses we'd specify our base comma our exponent. Let's take a look at how we can use recursion to also find a number raised to a power. And we might even find a way that will make it more efficient along the way. We'll start by the definition of what does it mean to take a number, and raise it to a power? For example, X represents a number raised to the N power.
This means that X is multiplied by itself N minus one times. For example, X to the fourth takes X times itself and it actually multiplies it by itself three times. There's three computations here, three times we use the multiplication. Let's see if we can think of a different way. If N is even, we can say that X to the N is equal to X to the N divided by two times X to the N divided by two. We haven't changed the end result.
We've just changed our approach to the problem. If N is odd, we still have X to the N divided by two times X to the N divided by two but now we need to multiply it by X, as well. Let's go back to our example of three raised to the fourth power. So three raised to the fourth power gives us 81. And there's three computations 'cause we have to multiply three by itself three times. Let's change this to say, three to the fourth is equal to three squared times three squared.
Which is still equal to 81. But, what we can do is we can take one of the three squareds, and we say that is three times three which is nine. So that's one multiplication. But now, we can substitute that value in for both of our three squareds. And now we do nine times nine, and that's 81. So this, only takes two multiplication steps. The benefit of this approach grows exponentially better with larger numbers. Let's try three to the eighth power.
Three to the eighth is three to the fourth times three to the fourth which is equal to three squared times itself three times. So in this case, we take the three squared, we replace it with a nine. Then, that's one multiplication. Then we replace each of these three squares with a nine. And so now we have three four times that we need to multiply nine. So that ends up with four multiplications. But we know that three to the eighth we'd have to actually multiply three times itself seven times.
So right here, we're saving three steps. All right, let's take a look at a program that uses recursion to find the value of a number raised to a power. I already have my package open and I've copied the power function dot Java file from my Exercise Files folder. I want to allow the user to enter in a number and the exponent. So I'm going to start in my main by adding a scanner class. Next, I'm going to put a message that says enter your base number and exponent.
Now I need to read those values in. So I'll allow them to enter in an integer, or a double. So I'm going to say double number is equal to in dot next double. In Java, if you read in an integer as a double it will just append to point zero. So that's fine. Now my exponent needs to be an imagery level so let's do int X equals int dot next int. Now that I have the values, what I want to do is print out the result of using my recursive function that we still have to define.
Let's go ahead and put our printline here that says power, that will be the name of our function. And we pass it the number and the exponent. Now I need to create my power method so I'm going to have it return a double and it's going to be called power. It takes in a double and it takes in an integer. The double represents the base value and N represents the power, or the exponent. Now, I'm going to create another variable Y. My base case is when N, or the exponent, gets down to zero.
So I'm going to say if N equals equals zero then I want to return 1.0. Otherwise, I'm going to say that Y is equal to a call to the power function. Here's my recursive portion. And this is going to pass it the value X, the number X comma and I'm going to take the exponent and divide it by two. Finally, I'm going to say Y is equal to Y times Y.
And then if the exponent is even so N divided by two is equal equal to zero. I'm sorry, not divided by, mod two the remainder. Mod two is equal equal to zero. Then, I want to return Y. Otherwise, I'm going to return X times Y. So if it is even, I don't need to multiply it by X again. If it's not even, then I do. Let's go ahead and give this a try.
Let's run our program. Oh, I do have to import my scanner class so let's do that first. Add the import. Okay, and now we can click Run. So let's go ahead and do three and four and we get the value 81 because three raised to the fourth power is 81. Let's try another one, let's run it again and let's do three and eight. And you can see we get six five six one. So it looks like our method is working and it seems like it's very fast.
So sometimes the recursive function does allow you to do things even quicker. So if you didn't follow along, go ahead and copy down the power function dot Java file from the Exercise Files folder, and give it a try.
Programmers involved in mathematical computations, such as mathematical induction, are probably the biggest users of recursion. You probably know some of the most common recursive problems; finding the factorial of a number and the Fibonacci series are both examples of recursive processes. In this course, staff instructor and Java expert Peggy Fisher explores programming solutions involving both of these problems. She reviews the concept of recursion, discusses approaches to solving problems using recursion, and examines some recursive examples.
- Defining recursion
- Reviewing recursive examples
- Converting decimal to binary
- Printing a LinkedList
- Writing a power function