- Write 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^{4} = 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
^{0}= 1; (anything to the power of 0 is 1). - To calculate A
^{n}, 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
^{n}. Then we can write recursive expression as**getPower(A, n) = A X getPower(A, n-1);**

## 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^{3} = 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.

Letpower(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^{8}= 2^{4}* 2^{4}; 2^{9}= 2^{4}* 2^{4}* 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);

/* * 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**