- Tail call optimization (꼬리 물기 최적화) 란?
- Tail recusrion (꼬리 물기 재귀함수)
- Tail recursion optimization 원리를 이용한 제어문 치환
- 결론
- 재귀 호출을 반복문으로 변경하기 위해서는 먼저 꼬리 물기 최적화 (Tail call optimization)가 되어 있어야 한다
- 반복 단계별 계산 결과를 반복이 끝날 때까지 어떤 변수에 계속 저장한다
Tail call optimization (꼬리 물기 최적화) 란?
- Tail call (꼬리 물기)이란
- 서브루틴의 호출을 프로시저(procedure)의 마지막 행위로 수행하는 것
- 즉, 서브루틴 호출 체인이 발생할 때 그 호출을 return 문에서 수행하는 것
- Tail call optimization (꼬리 물기 최적화)이란
- ‘호출된’ 함수에서 ‘호출한’ 함수로 되돌아온 뒤 아무것도 할 게 없다면 굳이 ‘호출한’ 함수로 되돌아올 필요가 없음
- 최적화가 되어 있다면 마지막으로 ‘호출된’ 함수에서 최초로 ‘호출한’ 함수로 바로 되돌아갈 수 있음
- low level 관점에서
- 서브 루틴이 호출될 때 반환 주소가 stack 에 push 되는데
- 꼬리 물기 최적화가 되어 있다면 반환 주소가 push 되지 않고 바로 상위 콜스택으로 반환될 수 있음
- 이를 가능하게 하기 위해서는 return 문에서는 stack push 가 필요한 별도의 연산자를 사용하면 안된다
- 연산에 필요한 모든 상태나 값들은 서브 루틴으로 넘겨야 한다
- 언어의 실행환경(컴파일러)이 제공해야 할 수 있으며 개발자가 임의로 적용할 수는 없다
꼬리 물기 최적화의 올바른 예
int factorial(int x, int acc = 1) { return (x <= 1? acc : factorial(x - 1, acc * x)); }
꼬리 물기 최적화의 잘못된 예
int factorial(int x) { return (x <= 0 ? 1 : x * factorial(x - 1)); }
Tail recusrion (꼬리 물기 재귀함수)
- Tail call의 특별한 형태로 마지막에 호출할 서브루틴이 자기 자신인 경우
Tail recursion optimization 원리를 이용한 제어문 치환
- 결국 Tail call optimizaiton을 이용하면 스택을 하나만 유지할 수 있음 -> 이를 스택 클리어라 부름
- 스택 클리어는 언어 구조상 보통 두 가지 경우로 구현
- 꼬리 물기 최적화
- 반복문을 이용
- 반복문은 매 iteration 마다 스택을 클리어하므로 무한루프를 돌 수 있음, 대신 남겨야 할 것은 변수로 저장
결국 재귀호출을 반복문으로 치환하기 위해서는 다음과 같은 조건이 만족되어야 한다
- 재귀에서는 반환포인트를 자동으로 처리하지만, 반복문에서는 직접 스택 구조를 작성해야 한다
- 재귀에서는 인자가 자동선언되므로 변수를 직접 제어할 일이 거의 없지만, 반복문에서는 필요한 변수를 선언하고 매 iteration 마다 초기화해야 한다.
factorial 함수를 위의 조건을 만족하도록 반복문으로 변경하면
int factorial(int x) {
int result = 1;
stack s = new stack();
int current = x;
do {
if (x <= 1) break;
result *= current;
stack.push(current - 1);
} while(current = stack.pop());
return result;
}
결론
다음과 같은 방법으로 재귀 호출을 반복문으로 치환할 수 있다
- 재귀호출을 반복문으로 고치려면 이미 재귀함수가 꼬리물기 최적화 형태로 되어있어야 한다.
- 꼬리물기 최적화가 끝나있는 함수는 return을 결과 변수에 취합하는 것으로 변경
- 재귀호출을 스택에 넣어주는 것으로 갈음하면 간단히 번역될 수 있다.