숫자의 거듭제곱 계산하기

JavaScript에는 어떤 숫자의 거듭제곱을 계산해 주는 내장된 pow 함수가 있긴 하지만 직접 유사한 함수를 효율적으로 재귀를 이용해 작성할 수 있습니다. 유일한 단점은 지수가 정수여야 한다는 것입니다.
xn x^n 을 계산하려고 한다고 가정합시다. 여기서 x x 는 임의의 실수이고 n n 는 임의의 정수입니다. n n 이 0이라면 x x 의 값이 무엇이든 간에 x0=1 x^0 = 1 이기 되기 때문에 문제는 쉽습니다. 이는 좋은 탈출 조건입니다.
그러면 이제 n n 이 양수일 때 어떻게 되는지 알아봅시다. x x 의 거듭제곱을 곱할 때는 지수를 더하면 됩니다. 임의의 밑수 x x 와 임의의 지수 a a b b 에 대해 xaxb=xa+b x^a \cdot x^b = x^{a+b} 입니다. 그러므로 n n 이 양수이고 짝수이면 xn=xn/2xn/2 x^n = x^{n/2} \cdot x^{n/2} 이 됩니다. y=xn/2 y = x^{n/2} 을 재귀적으로 계산하고자 할 경우 xn x^n yy y\cdot y 로 계산할 수 있습니다. n n 이 양수이고 홀수일 경우는 어떨까요? 그러면 xn=xn1x x^n = x^{n-1} \cdot x 이고 n1 n-1 은 0이거나 짝수인 양수가 됩니다. 방금 지수가 0이거나 짝수이면서 양수일 때 x x 의 거듭제곱을 계산하는 방법을 알아보았습니다. 이제 xn1 x^{n-1} 을 재귀적으로 계산하고 이 결과를 이용하여 xn=xn1x x^n = x^{n-1} \cdot x 를 계산할 수 있습니다.
n n 이 음수일 경우는 어떨까요? 그러면 xn=1/xn x^n = 1 / x^{-n} 이고 지수 n -n 은 양수가 됩니다. 그러므로 xn x^{-n} 를 재귀적으로 계산하고 그 역수를 구하면 됩니다.
위와 같은 관찰결과를 종합하여, xn x^n 을 계산하는 재귀 알고리즘을 구현하였습니다.
  • 탈출 조건은 n=0 n = 0 이고 x0=1 x^0 = 1 일 경우입니다.
  • n n 이 양수이고 짝수이면 y=xn/2 y = x^{n/2} 을 재귀적으로 계산한 후 xn=yy x^n = y \cdot y 를 계산합니다. xn/2 x^{n/2} 을 한 번만 계산하고, 이 재귀 호출의 결과를 그 자신과 곱함으로써 단 한 번의 재귀 호출만 해도 된다는 것을 주목하세요.
  • n n 이 양수이고 홀수이면 xn1 x^{n-1} 을 재귀적으로 계산하여 지수가 0이거나 양수이면서 짝수가 되게 합니다. 그러면 xn=xn1x x^n = x^{n-1} \cdot x 가 됩니다.
  • n n 이 음수이면 xn x^{-n} 을 재귀적으로 계산하여 지수가 양수가 되도록 합니다 그러면 xn=1/xn x^n = 1 / x^{-n} 이 됩니다.

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.
로딩 중