I had to develop a brute force, a recursive, divide and conquer, and transform and conquer algorithms for calculating the nth power of a, a^n, for an assignment. I got the first three done pretty easy but I'm completely stumped at how to do the transform and conquer algorithm.

I've been looking around and I was thinking of using modular exponentiation or exponentiation by squaring but I can't seem to find any recursive algorithm examples for how to do it and I can't figure out how to take something that is not recursive and make it recursive for example I found this modular exponentiation algorithm.

```
Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {
Bignum result = 1;
while (exponent > 0)
{
if ((exponent & 1) == 1)
{
// multiply in this bit's contribution while using modulus to keep result small
result = (result * base) % modulus;
}
// move to the next bit of the exponent, square (and mod) the base accordingly
exponent >>= 1;
base = (base * base) % modulus;
}
return result;
}
```

How could I take something like that and make it recursive? Or would a different algorithm be better for doing a recursive transform and conquer algorithm for finding a^n?

Thanks a bunch in advance.