SICP 트리 재귀

피보나치 수열은 트리재귀의 한예로, 피보나치 수열의 각 수는 그 이전 두 수의 합이다.

0,  1, 1, 2, 3, 5, 8, 13, 23 ...

피보나치 수열의 일반화는 다음과 같다.

Fib(n) = 0, n = 0

Fib(n) = 1, n = 1

Fib(n) = Fib(n-1) + Fib(n - 2)

피보나치 수열을 함수로 구현하면 다음과 같다.

function fib(n) {
	return n === 0
		: 0 
		? n === 1
		: 1
		? fib(n - 1) + fib(n - 2);
}

이와 같이 트리재귀 함수는 피보나치 수열을 구현하기에는 적합하지만, 계산에서는 매우 부적절한 면이 있다.

그것은 실제 계산시, 중복되는 계산이 지수적으로 증가한다는 것이다.

트리 재귀적 과정에 필요한 단계의 수는 트리의 노드 수에 비례하고, 필요한 공간은 트리의 최대 깊이에 비례한다.

피보나치 수를 구현할 때, 반복적 과정을 이용할 수 있다.

a와 b를 각각 fib(0) = 0, fib(1) = 1로 초기화하고 다음 규칙을 적용하여 a와 b를 적용해 나간다.

a ← a + b

b ← a

그러면 n에 대하여, fib(n) 은 a가 되고, fib(n + 1)은 b가 됨을 알 수 있다.

피보나치 수열을 반복적 계산으로 구현하면 다음과 같이 구현할 수 있다.

function fib(n) {
	return fib_iter(1, 0, n);
}

function fib_iter(a, b, count) {
	return count === 0
		: b
		? fib_iter(a + b, a, count - 1);
}

해당 함수는 선형반복 구조를 가지고 있다.

트리 재귀함수는 수치가 아닌 위계 구조로 구성된 데이터를 다룰 때, 강력하고 자연스러운 도구가 된다.