Topic
1. Factorial using Recursion2. Fibonacci using Recursion3. Tower of Hanoi4. GCD using Recursion5. Power using Recursion

Power using Recursion in C++

Calculate Power using Recursion in C++.

IntermediateRecursion ProgramsExample 5 of 5
power-using-recursion.cpp
1#include <iostream>
2using namespace std;
3

4// Recursive function to calculate power
5double power(double base, int exponent) {
6    // Base cases
7    if (exponent == 0) {
8        return 1;
9    }
10    if (exponent == 1) {
11        return base;
12    }
13    
14    // Handle negative exponent
15    if (exponent < 0) {
16        return 1.0 / power(base, -exponent);
17    }
18    
19    // Optimized: Divide and conquer
20    // If exponent is even: base^exp = (base^(exp/2))^2
21    // If exponent is odd: base^exp = base * (base^(exp/2))^2
22    if (exponent % 2 == 0) {
23        double half = power(base, exponent / 2);
24        return half * half;
25    } else {
26        double half = power(base, (exponent - 1) / 2);
27        return base * half * half;
28    }
29}
30

31int main() {
32    double base;
33    int exponent;
34    
35    cout << "Enter base: ";
36    cin >> base;
37    cout << "Enter exponent: ";
38    cin >> exponent;
39    
40    double result = power(base, exponent);
41    cout << base << "^" << exponent << " = " << result << endl;
42    
43    // Test various powers
44    cout << "\nVarious powers:" << endl;
45    cout << "2^10 = " << power(2, 10) << endl;
46    cout << "3^5 = " << power(3, 5) << endl;
47    cout << "5^-2 = " << power(5, -2) << endl;
48    cout << "10^0 = " << power(10, 0) << endl;
49    
50    return 0;
51}

Output

Enter base: 2
Enter exponent: 8
2^8 = 256

Various powers:
2^10 = 1024
3^5 = 243
5^-2 = 0.04
10^0 = 1

What's going on

The program demonstrates optimized recursive power calculation:

Divide-and-conquer approach
Handling even and odd exponents
Supporting negative exponents
Efficient O(log n) time complexity

Optimized recursion provides efficient power calculation.

Header Files Used

1.#include <iostream>
Provides cout and cin for input/output operations.

Understanding Power Calculation

Power Definition

:

base^exponent = base × base × ... × base (exponent times)
Example: 2^8 = 2 × 2 × 2 × 2 × 2 × 2 × 2 × 2 = 256

Optimization Idea

:

Instead of multiplying base exponent times
Use divide-and-conquer: base^exp = (base^(exp/2))^2
Reduces recursive calls significantly

Base Cases

Stopping Conditions

:

if (exponent == 0) {

}

if (exponent == 1) {

return base; // Any number to power 1 = itself

}

1return 1;  // Any number to power 0 = 1

How it works

:

Power 0: always returns 1
Power 1: returns base itself
Stops recursion
Essential base cases

Handling Negative Exponents

Negative Exponent

:

if (exponent < 0) {

}

1return 1.0 / power(base, -exponent);

How it works

:

Negative exponent: base^(-exp) = 1 / base^exp
Converts to positive exponent
Returns reciprocal
Handles negative exponents

Optimized Recursive Case

Even Exponent

:

if (exponent % 2 == 0) {

double half = power(base, exponent / 2);

}

1return half * half;

How it works

:

base^even = (base^(even/2))^2
Example: 2^8 = (2^4)^2 = 16^2 = 256
Reduces problem by half
More efficient

Odd Exponent

:

else {

double half = power(base, (exponent - 1) / 2);

}

1return base * half * half;

How it works

:

base^odd = base × (base^((odd-1)/2))^2
Example: 2^9 = 2 × (2^4)^2 = 2 × 256 = 512
Handles odd exponents
Maintains efficiency

Time Complexity

Efficiency

:

Naive: O(n) - n multiplications
Optimized: O(log n) - log n recursive calls
Much faster for large exponents
Divide-and-conquer benefit

Example

:

2^1000: naive needs 1000 operations
Optimized: only ~10 recursive calls
Significant improvement

When to Use This Approach

Best For

:

Large exponents
Performance-critical code
Mathematical computations
Efficient power calculation
Divide-and-conquer learning

Example Scenarios

:

Cryptography (modular exponentiation)
Scientific calculations
Algorithm optimization
Mathematical libraries
Performance-critical applications

Important Considerations

Divide-and-Conquer

:

Breaks problem in half
Reduces recursive calls
Logarithmic time complexity
Efficient algorithm

Exponent Types

:

Handles positive exponents
Handles negative exponents
Handles zero exponent
Comprehensive coverage

Precision

:

Uses double for decimal results
Handles fractional bases
Maintains precision
Suitable for various inputs

return 0;

This ends the program successfully.

PreviousGCD using Recursion