C Program to Find Power of a Number using Recursion

Here is a C program to find power of a number(a^b) using recursion. The power of a number(base^exponent)is the base multiplied to itself exponent times.

For Example
a^b = a x a x a .....x a(b times)
2⁴ = 2x2x2x2 = 16

Here we will solve this problem using recursion. We will first take base and exponent as input from user and pass it to a recursive function, which will return the value of base raised to the power of exponent(base^exponent).

Algorithm to find power of a number using recursion

Base condition of recursion : A⁰ = 1; (anything to the power of 0 is 1).

To calculate Aⁿ, we can first calculate A^n-1 and then multiply it with A(A^n = A X A^n-1).

Let getPower(int A, int n) is a function which returns Aⁿ. Then we can write recursive expression as getPower(A, n) = A X getPower(A, n-1);

Time Complexity: O(n)

C program to find power of a number using recursion

Below program first takes base and exponent as input from user using scanf function and stores it in integer variables. It uses a user defined function getPower, that takes base and exponent as input parameters and returns the value of base^exponent. To calculate base^exponent, function getPower calls itself recursively as getPower(base, exponent-1) to calculate base^exponent-1
For Example:
2³ = getPower(2,3) = 2 x getPower(2,2) = 2 x 2 x getPower(2,1) = 2 x 2 x 2 x getPower(2,0) = 2 x 2 x 2 x 1 = 8

#include <stdio.h>

int main(){
    int base, exponent, counter, result = 1;
    printf("Enter base and exponent \n");
    scanf("%d %d", &base, &exponent);
    
    result = getPower(base, exponent);
    
    printf("%d^%d = %d", base, exponent, result);
    return 0;
}

int getPower(int base, int exponent){
    if(exponent == 0){
        return 1;
    }
    return base * getPower(base, exponent - 1);
}

Output

Enter base and exponent 
4 0
4^0 = 1

Enter base and exponent 
3 4
3^4 = 81

C program to find power of a number using divide and conquer

To find the power of a number, we can use Divide and Conquer approach. A divide and conquer algorithm solves a problem in three steps.

It divides a problem into two or more sub problems. Such that each sub-problem is same as the original problem but for smaller data set.
It solve each sub-problem recursively and stores the solution of each sub-problem If required.
It combines the solutions of sub-problem to get the overall solution of original problem.

Let power(a, b) returns the value of a^b
  If b is even : power(a, b) = power(a, b/2)*power(a, b/2);
  if b is odd : power(a, b) = power(a, b/2)*power(a, b/2)*a;
For example: 
  2⁸ = 2⁴ * 2⁴;
  2⁹ = 2⁴ * 2⁴ * 2;
Once we calculated power(a, b/2), we don't have to calculate it again. We can simply square it.
Now, 
  If b is even : power(a, b) = power(power(a, b/2), 2);
  If b is odd : power(a, b) = power(power(a, b/2), 2)*a;

Below program contains a user defined function getPower, that takes base and exponent as input parameters and returns the value of base^exponent. Function getPower implements the divide and conquer algorithm mentioned above to calculate the power of a number.

getPower(A, n) = if n is even: getPower(A, n-1) X getPower(A, n-1); 
                 if n is odd: A X getPower(A, n-1) X getPower(A, n-1);

#include <stdio.h>

int main(){
    int base, exponent, counter, result = 1;
    printf("Enter base and exponent \n");
    scanf("%d %d", &base, &exponent);
    
    result = getPower(base, exponent);
    
    printf("%d^%d = %d", base, exponent, result);

    return 0;
}

int getPower(int base, int exponent){
    int result;
    if(exponent == 0){
        return 1;
    }
    result = getPower(base, exponent/2);
    if(exponent%2 == 0){
        /*Exponent is even */
        return result*result;
    } else {
        /*Exponent is odd */
        return base*result*result;
    }
}

Output