자바스크립트 꼬리물기 최적화

Tail recursion

언어 수준에서 지원해야한다.

사파리에서는 tail recursion을 구현할 수 있다.

const sum = v=>v + (v > 1 ? sum(v-1) : 0);
sum(3);

위와 같은 코드는 꼬리물기 최적화를 할 수 없다. 재귀함수를 실행하는 동안 메모리를 유지해야 하기 때문이다. 더하기 연산자가 꼬리물기 최적화를 방해하고 있다.(스택으로 기억하고 있어야 하기 때문)

꼬리물기 최적화를 하기 위해서는 리턴하고 함수 호출하는 사이에 메모리를 잡지 않도록 아무도 방해하지 않게 해야 메모리를 해제하고 리턴 포인트를 옮겨줄 수 있다.

⇒ 리턴과 함수콜만 남겨야 한다. 가장 많이 알려진 방법은 연산을 인자로 옮기는 것이다.

const sum = (v, prev = 0)=>{
	prev += v;
	return (v > 1 ? sum(v - 1, prev) : prev);
};
sum(3);

+와 같은 연산자 대신에 prev인자를 주어 현재 메모리를 해제하고 다음 함수의 인자 메모리로 넘긴다.(함수의 메모리는 인자와 지역변수이다.)

삼항연산자와 &&, || 연산자는 스택을 잡지 않는 연사자이다. tail recursion 대상이다. 왜냐하면 지연 평가를 하기 때문이다.

JS는 이미 ES6에 Tail recursive를 지원했다. 브라우저가 아직 구현하지 못했을 뿐.

함수 작성할 때 아예 습관을 재귀적인 로직이 있으면 언제나 꼬리물기 최적화가 일어날 수 있는 형태로 작성해야한다.

Tail recursion to loop

tail recursive한 함수는 기계적으로 loop로 바꿀 수 있다.

// tail recursion
const sum = (v, prev = 0)=>{
	prev += v;
	return ()
};

// loop
const sum = (v)=>{
	let prev = 0;
	while(v > 1){
		prev += v
		v--;
	}
	return prev;
}

그래서 loop문이 돌 때마다 스택을 clear해준다고 하는 것이다. 제어문의 loop가 돌 때마다 스택을 clear한다는 개념은 꼬리물기 최적화가 되어있는 함수로 옮겨보면 정확하게 이해할 수 있다.

꼬리물기 최적화가 지원되지 않는 언어는 굉장히 큰 재귀함수가 stack overflow로 죽어버리니까 개발자는 기계적으로 loop문으로 바꾸어야 한다.

재귀함수 ⇒ 꼬리물기 최적화된 재귀함수 ⇒ loop로 변경

프로그래머의 기본기라고 한다. 숙련하자!

출처: 코드스피츠