Find Power of a Number using Recursion in Java

Find Power of a Number using Recursion in Java.

---

Given two integers base and number, write a function to compute base^number. 
Assume that base and number are small and will not cause integer overflow.

Lets understand what is the input and the expected output.

Algorithm 

---

We will see both Iterative and Recursive approach.

In Iterative approach, initialize temp=1 and multiply the temp by base till the count of exponent.

In Recursive approach, we will break the problem into two parts, and only solve one portion of it.
Based on the exponent is even or odd, that is it is perfectly divided into two parts or not, return either multiples of result of each recursive call or add multiply remaining base to the result if it is not perfectly divisible into two parts.

base = 2, exponent = 8
(8/2=4)
only calculate 2^4 and multiply the result twice as that will give you 2^4 * 2^4 = 2^8.

base = 2, exponent = 7
(7/2 = 3)
only calculate 2^3 and multiply the result twice as that will give you 2^3 * 2^3 = 2^6.
Multiply the result with remaining 2 which will make it 2^7.


Find Power of a Number using Recursion in Java

---

package com.javabypatel.misc;

/*

Input: base=2 and number=8
Output: 256

Input: base=3 and number=1
Output: 3

Input: base=4 and number=0
Output: 1

 */
public class PowerFunction {

    public static void main(String[] args) {
        int base = 4;
        int number = 0;
        System.out.println(calculatePowerIterative(base, number));
        System.out.println(calculatePowerRecursive(base, number));
    }

    //Assuming number is within integer bounds and overflow will not happen
    //Iterative solution O(num)
    private static int calculatePowerIterative(int base, int number) {
        int result = 1;
        for (int i = 0; i < number; i++) {
            result *= base;
        }
        return result;
    }

    //Assuming number is within integer bounds and overflow will not happen
    //Recursive solution O(Log N)
    private static int calculatePowerRecursive(int base, int number) {
        if(number == 0) {
            return 1;
        }

        if(number == 1) {
            return base;
        }

        //Example: if the number is 8, this will calculate
        //base^4, base^2, base^1, base^0 = result
        //It will multiply the result twice. so no need to calculate base^4 * base^4 twice for number=8.
        int result = calculatePowerRecursive(base, number/2);

        //If the number is perfectly divided into two parts, then we just need a product of those two numbers
        //Example: 2^6 = 6/2 = 3 and 3 = 2^3 and 2^3
        //If the number is not perfectly divided into two parts, then we need a product of those two numbers and (* base)
        //Example: 2^7 = 7/2 = 3 and 3 = 2^3 and 2^3 (* remaining 2)
        if(number % 2 == 0) {
            return result * result;
        } else {
            return result * result * base;
        }

    }
}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.