C Program to Calculate Power Using Recursion

You can calculate power using recursion in C by defining a function like int power(int base, int exp) { if (exp == 0) return 1; else return base * power(base, exp - 1); } which multiplies the base by itself exp times recursively.

Examples

Inputbase = 2, exponent = 3

Output8

Inputbase = 5, exponent = 0

Output1

Inputbase = 3, exponent = 4

Output81

How to Think About It

To find the power of a number using recursion, think of the problem as multiplying the base number by itself repeatedly. The base case is when the exponent is zero, which always returns 1. For other cases, multiply the base by the result of the function called with the exponent decreased by one.

Algorithm

1

Get the base and exponent as input.

2

Check if the exponent is zero; if yes, return 1.

3

Otherwise, multiply the base by the result of the power function called with exponent minus one.

4

Return the result.

Code

c

#include <stdio.h>

int power(int base, int exp) {
    if (exp == 0)
        return 1;
    else
        return base * power(base, exp - 1);
}

int main() {
    int base = 2, exp = 3;
    printf("%d to the power %d is %d\n", base, exp, power(base, exp));
    return 0;
}

Output

2 to the power 3 is 8

Dry Run

Let's trace power(2, 3) through the code

1

Initial call

power(2, 3) checks if exp == 0 (false), returns 2 * power(2, 2)

2

Second call

power(2, 2) checks if exp == 0 (false), returns 2 * power(2, 1)

3

Third call

power(2, 1) checks if exp == 0 (false), returns 2 * power(2, 0)

4

Base case

power(2, 0) returns 1

5

Return from third call

power(2, 1) returns 2 * 1 = 2

6

Return from second call

power(2, 2) returns 2 * 2 = 4

7

Return from initial call

power(2, 3) returns 2 * 4 = 8

Call	Exponent	Return Value
power(2, 0)	0	1
power(2, 1)	1	2
power(2, 2)	2	4
power(2, 3)	3	8

Why This Works

Step 1: Base Case

When the exponent is zero, the function returns 1 because any number to the power 0 is 1.

Step 2: Recursive Case

For exponents greater than zero, the function calls itself with the exponent decreased by one, multiplying the base each time.

Step 3: Multiplying Results

Each recursive call multiplies the base by the result of the smaller problem until reaching the base case.

Alternative Approaches

Using a loop

c

#include <stdio.h>

int power(int base, int exp) {
    int result = 1;
    for (int i = 0; i < exp; i++) {
        result *= base;
    }
    return result;
}

int main() {
    printf("%d\n", power(2, 3));
    return 0;
}

This method uses iteration instead of recursion, which can be more efficient and avoids stack overflow for large exponents.

Using fast exponentiation (divide and conquer)

c

#include <stdio.h>

int power(int base, int exp) {
    if (exp == 0) return 1;
    int half = power(base, exp / 2);
    if (exp % 2 == 0) return half * half;
    else return base * half * half;
}

int main() {
    printf("%d\n", power(2, 3));
    return 0;
}

This method reduces the number of multiplications by splitting the exponent, making it faster for large exponents.

Complexity: O(n) time, O(n) space

Time Complexity

The function calls itself once per decrement of the exponent, so it runs in linear time relative to the exponent.

Space Complexity

Each recursive call adds a new layer to the call stack, so space used is proportional to the exponent.

Which Approach is Fastest?

The fast exponentiation method is faster with O(log n) time, while the simple recursion and loop methods are O(n).

Approach	Time	Space	Best For
Simple Recursion	O(n)	O(n)	Small exponents, easy to understand
Loop	O(n)	O(1)	Avoiding recursion overhead
Fast Exponentiation	O(log n)	O(log n)	Large exponents, performance critical