[algorithm] 개선된 거듭제곱 알고리즘

문제
문제링크(백준알고리즘 1629번)
백준 알고리즘에서는 A를 B제곱한 수를 C로 나는 나머지를 구하는 문제이다.
살짝 바꿔서, A를 base, B를 exponent, C는 94906249라고 하기로 한다.

풀이코드

function power(base, exponent) {
  if (exponent === 0) return 1;
  let tmp = power(base, Math.floor(exponent / 2));
  let result = tmp * tmp % 94906249;

  return exponent % 2 ? base * result % 94906249 : result;
}

풀이설명

시간 복잡도를 줄이기 위해 재귀함수를 써서 logN의 시간복잡도를 가지는 개선된 코드로 만들었다.
지수(exponent)를 절반씩 줄여나가면서 반복을 반으로 줄이는 것이 기본 로직이다.
단, exponent가 짝, 홀인 경우를 갈라서 써주면 된다.

시행착오

처음에는 지수(exponent)가 짝수일 때 재귀함수 호출 한 번, 홀수일 때 한 번, 이렇게 모두 재귀함수를 두 번 호출했다.
이러면 재귀를 호출한 의미가 없어진다.

2^7 = (((((2 * 2) * 2) * 2) * 2) * 2) * 2 // 재귀 없으면 곱하기 6번 진행
2^7 = 2 * (2 * ( 2 * 2)) * (2 * (2 * 2)) // 재귀 쓰면 곱하기 4번 진행

이런 식으로 계산을 줄이는 게 목적인데 나뉘 부분에서 각각 재귀를 호출해줬으니 시간복잡도가 개선되지 않았던 것이다.