학습목표
- 재귀적인 문제 해결 방법
- 일반 재귀와 꼬리 재귀의 차이를 이해하는가?
- 여러분이 사용하는 프로그래밍 언어가 꼬리 재귀 최적화를 제공하는지 아니라면 왜 못하는지 학습하세요.
- 연결 리스트를 꼬리부터 머리까지 출력하는 코드를 작성하라.
재귀적인 문제 해결 방법
- 1) 반복되는 로직을 확인하여 작게 구분하여 재귀함수를 만든다 → 왠만한 반복문은 재귀함수로 작성 가능하다.
- 2) 종료조건을 명시한다. (f(0),f(1) 아 이게 종료조건이구나.)
- 장점
- 가독성이 좋음
- 코드가 짧음
- 각 단계의 변수 상태가 자동 저장됨.
- 코드 검증도 쉬움
- 단점
- 재귀적 문제 분석/설계가 안 직관적
- 맹목적인 믿음이 필요
- 스택 오버플로 발생 가능
- 함수 호출에 따른 과부하(모든 함수 호출에는 성능저하가 있을 수 있다.)
- 읽기 좋은 코드 작성이 기본!
- 기본적으로 재귀 함수를 사용하는 게 나은 방법
- 가독성이 좋고 유지보수가 쉬운 코드가 더 중요
- 다음과 같을 경우 반복분으로 변환
- 스택 오버플로가 날 가능성이 있는 경우
- 성능 문제가 일어날 경우, 확인된 경우
- 모든 재귀 함수는 반복문을 작성 가능
- 복잡한 경우 스택 등의 데이터 구조를 사용해야 함.
일반 재귀와 꼬리 재귀의 차이를 이해하는가? 여러분이 사용하는 프로그래밍 언어가 꼬리 재귀 최적화를 제공하는지 아니라면 왜 못하는지 학습하세요.
- 꼬리 호출(tail call)
- 함수 코드 제일 마지막에서 다른 함수를 호출하는 경우
- 그 후에 실행하는 명령어가 없음
- 스텍 프레임이 존재하는 이유
- 함수에서 사용중인 변수 값을 유지하기 위해
- 타 함수 호출 후 반환되면 스택에 저장했던 값을 되돌려 사용
- 꼬리 호출의 경우는 타 함수로부터 반환 후 더 이상 연산이 없음
- 따라서 스택 프레임에 저장해 놓은 변수 값을 재사용하지 않음 → 일반 재귀와 꼬리 재귀의 차이
- 이런 경우 컴파일러가 스택 프레임을 따로 안 만드는 최적화를 하기도 함
- 꼬리 호출 제거 (tail call elimination)
- 꼬리 호출 최적화 (tail call optimization)
- VM 기반 언어는 case by case임
- JAVA는 현재까지 제공하지 않고 있음.
- Golang도 제공하지 않고 있음.
- 코틀린은 제공하고 있음.
- 꼬리 재귀 (tail recursion)
- 꼬리 호출의 특수한 경우
- 마지막에 호출하는 함수(꼬리 호출)가 자기 자신(재귀)
- 꼬리 호출과 똑같은 최적화가 적용됨.
연결 리스트를 꼬리부터 머리까지 출력하는 코드를 작성하라.
// 1. prev, curr, curr.next(next)
// 2. recursive call 문제를 작게 만들어서 해결
private void reverse(){
LinkedNode head = this.head;
this.head = recursiveReverse(head);
this.tail = head;
}
private LinkedNode recursiveReverse(LinkedNode node){
// 종료조건
if(node == null || node.next == null){
return node;
}
LinkedNode newHead = recursiveReverse(node.next);
node.next.next = node;
node.next = null;
return newHead;
}