AlgoInsight

DSA problem

Power of a Number Using Recursion

EasyRecursionPattern: Divide and ConquerbeginnerFree

Given two integers base and exp, compute base^exp (base raised to the power exp) using recursion.

The naive recursive approach computes power(base, exp) = base * power(base, exp - 1) with base case power(base, 0) = 1, which runs in O(exp) time. The optimized approach uses exponentiation by squaring: if exp is even, power(base, exp) = power(base * base, exp / 2); if exp is odd, power(base, exp) = base * power(base, exp - 1). This reduces the time to O(log exp) - a massive improvement for large exponents.

Exponentiation by squaring powers modular exponentiation (critical in RSA encryption), matrix exponentiation (computing Fibonacci numbers in O(log N)), and countless competitive-programming problems. It is a first taste of divide-and-conquer optimization.

Examples

Example 1
Input: base = 2, exp = 10
Output: 1024
Explanation: 2^10 = 1024. Exponentiation by squaring computes it with about log2(10) multiplications instead of 10, by repeatedly squaring the base and halving the exponent.
Example 2
Input: base = 3, exp = 5
Output: 243
Explanation: 5 is odd, so peel off one factor: 3 * power(3, 4). 4 is even, so square: power(9, 2) -> power(81, 1) -> 81. Result: 3 * 81 = 243.
Example 3
Input: base = 7, exp = 0
Output: 1
Explanation: The base case: any number raised to the power 0 is 1.

Constraints

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

recursionmathdivide-and-conquer

Browse all DSA problems