[알고리즘] 재귀함수를 이용한 거듭제곱

거듭제곱에 위와 같은 규칙이 있다는 것을 이해하고 코드를 작성하자.

function power(base, exponent) {
  if (exponent === 0) return 1;
  // 모든 수의 0제곱은 1이다

  const half = parseInt(exponent / 2);
  const temp = power(base, half);
  const result = (temp * temp) % 94906249;

  if (exponent % 2 === 1) return (base * result) % 94906249;

  return result;
}