skagmltn7
commented
1 year ago 재귀
static int fact(int n)
{
if(n < 2) return 1;
return n * fact(n-1);
}
/*
(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0)))) // 여기까지 스택쌓임
(* 3 (* 2 (* 1 1))) // 스택빠지기 시작
(* 3 (* 2 1))
(* 3 2)
6
*/
- 재귀 함수 호출 시 정지조건에 충족할 때까지 함수를 계속 호출한다.
- 함수를 호출할 때마다 파라미터, 리턴값, 리턴 후 돌아갈 위치 등이 스택에 쌓이게 된다.
- 호출당한 함수가 호출한 함수에게 자신의 결과값을 반환하고 호출한 함수는 그 값을 연산하여 결과값을 도출한다. 그 값을 다시 자신을 호출한 함수에게 전달한다.
- 장점: 코드가 짧아지고 내용도 직관적으로 파악할 수 있어 가독성이 높아진다
- 단점: 많은 재귀 함수가 스택에 쌓였을 경우 stack overflow가 발생할 수 있다.
꼬리호출
static int fact(int n){
return fact_tail(n, 1);
}
static int fact_tail(int n, int total){
if(n < 1) return total;
return fact_tail(n - 1, n * total);
}
/*
(fact 3)
(fact_tail 3 1)
(fact_tail 2 3)
(fact_tail 1 6)
(fact_tail 0 6)
6
*/
- 재귀함수의 단점을 보완하기 위한 방법
- 재귀함수는 함수를 호출 시 새로운 스택메모리를 할당하게 되는데 꼬리호출은 별도의 연산없이 결과를 반환하여 현재 함수의 스택메모리를 재사용한다.
- 마지막 꼬리에 곱셈 연산을 마친 값이 저장되기 때문에 호출한 함수들에게 그 값을 그대로 반환해준다.
- 즉, 마지막 꼬리 함수의 결과값이 함수의 최종결과값이 된다.
꼬리 호출의 최적화
스칼라, 코틀린 등의 경우 다음과 같이 컴파일러가 자체적으로 꼬리 재귀 최적화를 한다.
// 이코드를
static int fact_tail(int n, int total){
if(n < 1) return total;
return fact_tail(n - 1, n * total);
}
// while 반복문으로 자동 최적화하여 바이트코드로 변환함
static int fact_tail(int n, int total){
while(n != 1) {
int var = total * n;
--n;
total = var;
}
return total;
}그러나 자바에서는 스택 프레임의 수에 의존하는 몇몇 jdk클래스가 존재하는데 프레임을 변경했을 때 오류가 발생할 수 있기 때문에 자동 꼬리 호출 최적화를 지원하지 않는다. 자바8의 람다식과 함수형 인터페이스를 사용하면 내부반복으로 직접 꼬리호출을 최적화할 수 있다.
문제
재귀와 꼬리 호출의 차이점과 꼬리 호출은 어떻게 최적화가 되는 걸까요?
contents - 세부 내용
예전에 찾아본 적이 있었는데 책에는 자세한 내용이 없는 것 같아 이슈로 삼았습니다.
참고
582p