SICP 거듭제곱

재귀적 정의

b^n = b * b ^ (n-1)

b^0 = 1

거듭제곱의 재귀적 정의를 함수로 구현하면 다음과 같다.

function expt(b, n) {
	return n === 0
	: 1
	? b * expt(b, n - 1);
}

위 함수는 선형 재귀적 과정으로 구현한 것이고, 반복적 과정으로 변경한 것은 아래와 같다.

function expt(b, n) {
	return expt_iter(b, n, 1);
}

function expt_iter(b, counter, product) {
	return counter === 0
	: product
	? expt_iter(b, n - 1, product * b);
}

하지만 여기서, 연속제곱을 이용하면 거듭제곱에 필요한 단계 수를 줄일 수 있고, 다음과 같이 정의된다.

b^n = (b^n/2)^2 → n이 짝수

b^n = b * b^(n -1) → n이 홀수

function fast_expt(b, n) {
	return n === 0
	: 1
	? is_even(n)
	: square(fast_expt(b, n / 2))
	? b * fast_expt(b, n - 1);
}