Fast exponentiation

Challenge

Implement:

long long fast_pow(int base, int exp);

Return base raised to exp (exp >= 0) using recursive exponentiation by squaring. The result fits in long long.

Input format

base, exp >= 0.

Output format

base^exp.

Constraints

Halve the exponent each call.

Starter code

#include <stddef.h>
/* base raised to exp (exp>=0) via recursive fast exponentiation (exponentiation by squaring). Result fits long long. */
long long fast_pow(int base,int exp){ (void)base;(void)exp; return 1; }

Common mistakes

Recomputing the recursive half twice instead of once; mishandling odd exponents.

Edge cases to handle

exp==0 returns 1 for any base.

Background lessons

• Recursive number theory