재귀함수(recursion)
- 함수가 '자기 자신'을 호출하는 경우, 이를 '재귀함수'라고 한다
- 큰 목표 작업을 간단한 작업 구조로 나눌 수 있을 때 유용한 프로그래밍 패턴
- 문제를 동일한 구조의 더 작은 문제로 나누어보고, 작은 문제를 해결함으로써 전체 문제를 해결하는 방법
- 코드가 간결하고 이해도를 높일 수 있다, 유지/보수가 쉬움
- 탈출조건: 언제 재귀를 끝낼 것인가(루프의 중지)
- 호출
- 문제의 분기점을 어떻게 정할 것인가
- 예외 처리
- 결과
- 값을 반환하는 return문의 위치 (return 되지 않으면 undefined 출력)
- 모든 경우의 수를 따지고 있는가 (예상하지 않는 부분에서의 return으로 재귀의 중단)
1. 재귀 함수의 기초
- base case: 더 이상 쪼갤 수 없는 명확한 결과값을 제시
- recursive case: 목표 작업을 위해 base case에 도달할 때까지 이어지는 단계
- recursion depth: 재귀의 깊이, 중첩 호출의 최대 개수, 실행 컨텍스트 수의 최대값과 동일
2. 문제를 재귀적으로 사고하기
- 재귀 함수의 입력값과 출력값 정의하기
- 문제를 쪼개고 경우의 수를 나누기
- 단순한 문제 해결하기 : 재귀의 기초(base case), 이를 통해 재귀의 탈출 조건을 구성
- 복잡한 문제 해결하기
- 코드 구현하기
function recursive(input1, input2, ...) {
// Base Case : 문제를 더 이상 쪼갤 수 없는 경우
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive Case
// 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
// 예1. someValue + recursive(input1Changed, input2Changed, ...)
// 예2. someValue * recursive(input1Changed, input2Changed, ...)
}
//factorial 함수를 예시로 보자
function facto(n) {
// 0!은 1이다
if(n <= 0) {
return 1;
}
// 3!이라면, 3*2*1
return n * facto(n - 1);
}
// 조건부 연산자를 활용한 축소코드
function facto(n){
return n ? n * facto(n-1) : 1;
}
3. 재귀 함수의 활용
- 트리 구조에 재귀 함수를 활용
- JSON 구조에 재귀 함수를 활용
- DOM 구조에 재귀 함수를 활용
4. 재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
- 실행 컨텍스트는 메모리를 차지하기 때문에, 재귀 함수 사용시 메모리 요구사항에 유의해야 한다.
- 깊이(depth)를 늘리면 깊이가 줄어들 때마다 depth 만큼의 실행 컨텍스트가 저장될 메모리 공간 필요 → 반복문 기반 알고리즘을 통해 메모리 사용 절약 가능(=함수 호출 비용의 절감)
5. 추가적으로 생각 해 볼 재귀의 주제
- 꼬리 재귀 (tail recursion in js)
- 하노이의 탑 재귀 (js tower of hanoi in recursion)
- 조합 재귀 함수 (js combination in recursion)
