거듭제곱 리턴

처음 시도했던 방법
메모이제이션과 재귀함수를 써보려고 함.
뭐가 문제인지 nan이 자꾸 떴다.
exponent가 0이거나 1이면 메모에 있는 값이 반환이 되는데, 재귀함수 부분이 잘못된듯...

function power(base, exponent) {
  //두수 입력 : base, exponent
  //거듭제곱 리턴 base를 exponent만큼 곱한 수 리턴
  let memo = [1, base]; //0제곱은 1, 1제곱은 자기자신
  const recur = (base, exponent) => {
    if(memo[exponent] !== undefined) return memo[exponent];
    //recur case: exponent -1씩 해서 base * base
    else {
      memo[exponent] = (base * recur(exponent-1)) % 94906249;
    }
    recur(exponent-1);
  }
  return memo[exponent] % 94906249;
}

WoW

2*2 %94906249 하면 4가 나온다.

저 수로 나누고 나머지를 구하면 제몫이 나오나봄...
왜 하필 저 수인가 했다.

레퍼런스를 보고, 스터디 시간에 이해한 후 작성한 답변
핵심은
1. 값을 곱해나가는 과정에서도 저 94906249로 나눈 나머지값으로 계산을 해야한다는 것.
2. for문 돌릴때 exponent만큼 다 돌리지 않는다.
이건 거듭제곱의 특성을 이용한 것인데, 구할 값의 반절만 구해놓고 그 수를 두번 곱하면 값이 나온다. 이렇게 글로 표현하니까 이상한데...
예를 들면 2의 10제곱을 구한다 할때, 2의 5제곱만 구하고 이걸 두번 곱한다.
2의 5제곱은 32이다. 그리고 32 * 32하면 1024가 나온다.
그리고 당연하게도 1024는 2의 10제곱을 구한 수이다.
3. for문 작성할때 exponent와 같을때까지 돌려야한다!! 그래야 딱 반절임
i <= Math.floor(exponent/2) 이부분...
4. exponent의 반절만큼 for문을 돌릴 때 소수점을 버리도록 했다.
exponent가 홀수일때를 대비한 것. 홀수라면 거듭제곱 한번 덜한거니까 base를 한번 더 곱해주면 된다.

function power(base, exponent) {
  //두수 입력 : base, exponent
  //거듭제곱 리턴 base를 exponent만큼 곱한 수 리턴
  //0제곱은 1
  //base를 exponent의 절반만 계산하고 그 결과값을 두번 곱하면 최종결과값이 나온다.
  let half = 1;
  if(exponent === 0) return 1;
  for(let i = 1; i <= Math.floor(exponent/2); i++) {
    half = half * base % 94906249;
  }
  if(exponent % 2 === 0) {
    return half * half % 94906249;
  } else {
    return half * half * base % 94906249;
  }
}