Integer power by recursion

Challenge

Raise an integer to a non-negative power using recursion and the binary-exponentiation (square-and-halve) trick.

Task

Implement long ipow(int base, int exp) recursively, where exp >= 0. Use the identity: ipow(b, e) = 1 when e == 0; ipow(b*b, e/2) when e is even; b * ipow(b, e-1) when e is odd. This keeps the recursion depth at O(log exp).

Input

An int base and a non-negative int exp.

Output

Returns base^exp as a long.

Example

ipow(2, 10)   ->   1024
ipow(3, 0)    ->   1
ipow(5, 3)    ->   125
ipow(10, 6)   ->   1000000

Edge cases

• exp == 0 returns 1 for any base (including base 0, by convention).

Rules

• The implementation must be recursive (no plain multiplication loop).

Why this matters

A clean recursive function is the entry point to dynamic programming. Doing power as iterate-vs-recurse is the cleanest example.

Input format

An int base and a non-negative int exp.

Output format

base raised to exp, as a long.

Constraints

Must be recursive. exp is non-negative; base^0 == 1.

Starter code

long ipow(int base, int exp) { /* TODO */ return 0; }

Common mistakes

Stack overflow at large exp if you do the naïve linear recursion.

Edge cases to handle

exp == 0 → 1. base == 0, exp == 0 → 1 (convention).

Complexity

O(log exp).

Background lessons

• Recursion — base case + smaller subproblem
• Functions

Up next

• Factorial
• Nth Fibonacci