[es6] 꼬리물기 최적화 (재귀함수)

"꼬리물기 최적화"는 프로그래밍에서 재귀 함수의 성능을 최적화하는 기법 중 하나입니다.

이 기법은 재귀 함수가 끝날 때 함수 호출 스택에서 이전 호출들을 제거하여 스택 오버플로우를 방지하고 메모리 사용을 최적화합니다.

꼬리물기 최적화의 핵심 아이디어는 "꼬리 재귀" 함수를 작성하는 것입니다. 

꼬리 재귀 함수는 재귀 호출이 함수의 마지막 작업으로 수행되는 경우를 의미합니다. 

따라서 꼬리 재귀 함수를 호출하면 현재 함수 호출 스택에 남아 있는 정보가 필요하지 않습니다. 

이를 통해 스택을 계속해서 쌓지 않고 재귀 함수를 최적화할 수 있습니다.

꼬리물기 최적화의 예시를 살펴보겠습니다. 

아래는 1부터 10까지 더하기 계산하는 재귀 함수의 비효율적인 버전과 꼬리 재귀 버전입니다.

비효율적인 재귀함수

const sum =(v)=> v > 1 ? v + sum(v-1) : 1;
console.log(sum(10));

꼬리 재귀함수

const sum = (v, acc)=> v > 1 ? sum(v - 1, acc + v) : acc + 1;
console.log(sum(10));

꼬리 재귀 함수에서는 재귀 호출 이후에 인자로 덧셈을 수행하므로 재귀 호출 이후에 추가적인 작업이 필요하지 않습니다.

따라서 함수 호출 스택이 계속해서 쌓이지 않고 최적화됩니다.

그러면 꼬리 재귀함수는 for 문으로 기계적으로 변환이 가능합니다.

꼬리 재귀함수 -> for 문을 변환

let i = 10;
let acc = 0;
for(i ; i > 1; i--) {
    acc += i;
}
acc += 1;
console.log(acc);

꼬리 재귀함수와 꼬리재귀 함수를 for 문으로 변경한 코드를 자세히 보시면 기계적으로 변환된다는 것을 알수 있습니다.

결론

복잡한 알고리즘을 정복하기 위해서 꼬리 재귀함수로 만든다음 for 문으로 기계적으로 변경하면 됩니다.