1/**
2* Calculate a^n in O(logn) time, instead of O(n) time with naive approach.
3**/
4public static long powerRecursive(int base, int exponent){
5 if(exponent == 0) return 1;
6 return (exponent % 2 == 0) ?
7 powerRecursive(base, exponent / 2) * powerRecursive(base, exponent / 2)
8 : base * powerRecursive(base, (exponent - 1) / 2) *
9 powerRecursive(base, (exponent - 1) / 2);
10}