# Calculate the power of a number with recursion using divide and conquer approach

As we all know, recursion is a programming technique where a function calls itself where the solution is achieved by solving sub problems of it.The best example of it would be solving the **tower of Hanoi problem**.

So when it comes to calculating the power of the number , the recursive algorithm can be thought as,

pow(n,x) => n*pow(n,x-1)

and the base case would be if **x==0 , then return 1;**

since any numbers 0th power is always 1.

so the recursive function is ready for calculating the power of a given number.

```
public static void main(String[] args) {
// the driver code
System.out.println(pow(8,0)); // output 1
System.out.println(pow(5,3)); // output 125
System.out.println(pow(2,10)); // output 1024
}
public static int pow(int num, int x) {
if (x == 0) return 1;
return num * pow(num, x - 1);
}
```

whats mostly important here is the run-time of the algorithm. This approach feels good and there are x-1 recursive calls needed to calculate the power. so the run-time of the algorithm is in linear scale.we can achieve a run-time in logarithmic scale when we use divide an conquer approach.

### Use of divide an conquer

As Wikipedia says,it is an algorithm design paradigm based on multi-branched recursion. A divide-and-conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly.This is again an extended version of recursion where we can make the run-time of the algorithm in **logarithmic scale**.

The idea is really simple, that is we can

but now we have to think of two scenarios where n is odd and n is even

- when n is even the above formula can be used.
- When n is odd we have to consider it as follows, its just mathematics

and the function would certainly turn on to this,

```
public static void main(String[] args) {
// the driver code
System.out.println(pow(8, 3)); // output 512
System.out.println(pow(5, 3)); // output 125
System.out.println(pow(2, 10)); // output 1024
}
public static int pow(int num, int x) {
//the base case
if (x == 1) return num;
//if x is even number
if (x % 2 == 0) {
//calculate the half of the power
int k1 = pow(num, x / 2);
//square the half of the power
return k1 * k1;
} else {
// if x is odd
// calculate the power as derived in the equation
int k1 = pow(num, (x - 1) / 2);
return k1 * k1 * num;
}
}
```

### Call stack of the algorithm

For example lets consider **pow(k,10)**

```
pow(k,10)
k1=pow(k,5) ; return k1*k1 that is power of 10
k1= pow(k,2); return k1*k1*K that is power of 5
k1=pow(k,1) ; return k that is power of 1;
```