C Program to Find Power of a Number using Recursion

  • Write a C program to find power of a number(ab) using recursion.

The power of a number(baseexponent)is the base multiplied to itself exponent times.
For Example
ab = a x a x a .....x a(b times)
24 = 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(baseexponent).

Algorithm to find power of a number using recursion
  • Base condition of recursion : A0 = 1; (anything to the power of 0 is 1).

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

  • Let getPower(int A, int n) is a function which returns An. 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 baseexponent. To calculate baseexponent, function getPower calls itself recursively as getPower(base, exponent-1) to calculate baseexponent-1
For Example:
23 = 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

/*
* C Program to find power of a number (a^b) using recursion
*/
#include <stdio.h>
#include <conio.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);
    getch();
    return 0;
}
/*
 * Function to calculate base^exponent using recursion
 */
int getPower(int base, int exponent){
    /* Recursion termination condition,
     * Anything^0 = 1
     */
    if(exponent == 0){
        return 1;
    }
    return base * getPower(base, exponent - 1);
}

Program 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 ab
  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: 
  28 = 24 * 24;
  29 = 24 * 24 * 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 baseexponent. 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);
/*
* C Program to find power of a number (a^b) using recursion
*/
#include <stdio.h>
#include <conio.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);
    getch();
    return 0;
}
/*
 * Function to calculate base^exponent using recursion
 */
int getPower(int base, int exponent){
    /* Recursion termination condition,
     * Anything^0 = 1
     */
    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;
    }
}

Program Output
Enter base and exponent 
5 4
5^4 = 625

Related Topics
C program to calculate power of a number
C program for palindrome check using recursion
C program to reverse a number using recursion
C program to find factorial of a number using recursion
C program to reverse a number
C program to reverse a string using recursion
C program to reverse an array using recursion
C program to find sum of digits of a number using recursion
List of all C Programs