Salfade logo

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

Algorithms Java Programming

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;


Related articles