In this tutorial, I am going to discuss how to calculate power using recursion.
Problem statement – Write a code to implement function pow(x, n), which calculates x raised to the power n (i.e. x^n). In this problem, We don’t have to use in-built function Math.pow.
For example:
Example 1:
Input: x = 2.00000, n = 3
Output: 8
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
In Java, we can easily calculate the power of any number using java.lang.Math.pow() method. It returns the result after calculating the value of the first argument raised to the power of the second argument.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Example using Math.pow() method public class Power { public static void main(String[] args) { /* In this code, we are calculating the result of 2 to the power of 3. Input: 2^3 Output: 8 */ System.out.println(Math.pow(2, 3)); } } |
Now, Let’s think about how we can calculate the power of a number without using Math.pow() in java.
In this tutorial, I am going to explain the iterative and recursive approaches to calculate the power of a number. Also, at the end of this tutorial, I have shared the link to a video tutorial.
Calculate Power of a Number – Iterative Approach
Let’s start with the easiest approach. The easiest approach is to run a loop from 1 to n (where n is the exponent). Declare one variable (result) and initialize with 1. Then in each iteration multiply the value of the base with the value of the result.
To handle the case where the value of n is negative. Run a loop from 1 to n (ignoring negative sign). Calculate the result and finally divide the result by 1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//Function to calculate power of a number - Java Code public double myPow(double x, int n) { //Declare result variable and initialized with 1 double result = 1; //Run a loop from 1 to n for(int i = 1; i <= Math.abs(n); i++) { result = result*x; } //Handlin negative case (2 ^ -3) if(n < 0) result = 1/result; return result; } |
Calculate Power using Recursion – Java Code
We have discussed the iterative approach and it’s very straightforward. Let’s calculate the power of a number using recursion. If you are not familiar with the concept of recursion then check my previous tutorials on recursion.
Recursion vs Iteration – Difference between recursion and iteration
Programming questions on recursion
In recursion, the function will call itself until the base condition is not reached. So, when we solve certain problems using recursion it is important to define the base condition else the function will call itself infinitely (Once the allocated memory is full it will throw stack overflow exception).
In this example, I have just converted the iterative version of code to its recursive version. The time complexity of this approach is O(n).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
//Calculate power using recursion public double myPow(double x, int n) { //Call helper method to calculate power double result = helper(x, Math.abs(n)); //If n is negative if(n < 0) result = 1/result; return result; } public double helper(double x, int n) { if(n <= 0) { return 1; } //Recursively compute the value return x * helper(x, n-1); } |
How we can improve this code further? For a large value of n, the previous code will throw a time limit exceeded exception. In this example, Let’s discuss how we can solve this problem in O(logn) time complexity.
Suppose we have to calculate the power of 210. To calculate the power we can write them as (2*2)5. In this way, we have reduced the computation steps.
Now let’s take the case of odd 211. For this, we can write as 2 * (2*2)5. Using this logic we can solve this problem efficiently.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//Calculate power of a number in O(logn) time complexity public double myPow(double x, int n) { if(n < 0) return 1.0/helper(x, Math.abs(n)); return helper(x, n); } public double helper(double x, int n){ if(n == 0) return 1; if(n == 1) return x; if(n % 2 == 0) return helper(x * x, n/2); return x * helper(x * x, n/2); } |
In this video tutorial, I have explained how we can calculate the power in java using Math.pow() method.
Calculate power of a number using recursion – video tutorial
