함수형 프로그래밍 - 트램폴린(Trampoline)
트램폴린(Trampoline) 트램폴린이란? 보통의 재귀 함수는 꼬리 재귀 최적화로 스택 오버플로우를 방지할 수 있다. 하지만 각 함수가 서로를 참조하는 상호 재귀 함수는 꼬리 재귀 최적화가 불가능하다. 트램폴린은 함수의 지연 처리를 이용해 상호 재귀 함수에 꼬리 재귀 최적화를 적용시킬 수 있다. thunk: () => Bounce[A] 는 함수를 바로 실행하지 않고 지연 처리시킨다. trampoline(evenWithTrampoline(5)) 의 동작을 살펴보자. n 이 5 → 4 → 3 → 2 → 1 → 0 이 되면 oddWithTrampoline(0) 에서 Done(false) 를 리턴한다. 그러면 다시 반대로 evenWithTrampoline(1) 에선 More(() ⇒ Done(false)) 를 리턴한다. oddWithTrampoline(2) 에선 More(() ⇒ More(() ⇒ Done(false))) 를 리턴한다. 이렇게 More 이 중첩되서 쌓이고, n 개 중첩된 More 를 trampoline 에서 인자로 받게 된다. trampoline(More(() ⇒ More(() ⇒ More(…)))) trampoline 함수는 꼬리 재귀 함수다. More 인 경우 thunk 의 결과값을 인자로 넘기기 때문에(acc 값) 콜스택이 쌓이지 않는다. 결국 콜스택을 쌓지 않고 More 을 모두 깐 뒤, 최종 Done 의 값을 얻어올 수 있다.