1.재귀(recursion)함수
- 함수가 '자기 자신'을 호출하는 경우 '재귀함수'라 부른다.
- 재귀란 큰 목표 작업을 간단한 작업 여러 개로 나눌 수 있을 때 유용한 프로그래밍 패턴으로 쉽게 말하면 '비슷한 경우의 문제를 쪼개어서 생각하는 것'이다.
재귀함수를 만들 때, 꼭 집고 넘어가야하는 부분.
- 탈출조건 : 언제 루프를 중지할 것인가(★★★★★)
- 호출
- 문제를 쪼개는 지점을 어떻게 정할 것인가(분기점)
- 예외 처리
- 결과
- 값을 반환하는 return문 위치 (명시하지 않으면 undefined 리턴)
- 모든 경우의 수를 따지고 있는가? (return 문으로 인한 즉시 중단 대처)
1) 재귀함수 템플릿
-
재귀의 베이스(base case)
- 더이상 쪼갤 수 없는 명확한 결과값을 제시하는 경우
-
재귀 단계(recursive case = recursive step)
- 목표 작업을 위해 재귀의 베이스에 도달할 때까지 이어지는 동작
-
일반적인 재귀함수 템플릿
function recursive(input1, input2, ...) {
// 재귀의 기초 (base case)
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive Case
// 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
// 예1. someValue + recursive(input1Changed, input2Changed, ...)
// 예2. someValue * recursive(input1Changed, input2Changed, ...)
}- 재귀의 깊이(recusion depth)
- 가장 처음 하는 호출을 포함한 중첩 호출의 최대 개수
- 깊이는 스택에 들어가는 실행 컨텍스트 수의 최댓값과 동일하다.
2) 재귀함수의 장점
- 작업을 단순화하고 간단하게 만들 수 있다.
- 코드가 간결해지고 짧아진다.(if문 대신 조건부 연산자(?) 등을 활용하여 축소 가능)
// 팩토리얼(n!) 재귀함수
function factorial(n){
if ( n === 0 ) {
return 1
}
return n * factorial(n-1)
}
// 조건부 연산자를 활용한 축소코드
function factorial(n){
return n ? n * factorial(n-1) : 1;
}- 이해도를 높일 수 있으며, 유지보수가 쉬운 코드 생성 가능
3) 재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
- 실행컨텍스트는 메모리를 차지하기 때문에, 재귀 함수 사용시 메모리 요구사항에 유의해야한다.
- 깊이(depth)를 늘리면 깊이가 줄어들 때마다 depth 만큼의 실행 컨텍스트가 저장될 메모리 공간 필요 → 반복문 기반 알고리즘을 통해 메모리 사용((=함수 호출의 비용) 절약 가능
4) 재귀적 순회(recursive traversal)
5) 재귀적 구조
- 자기자신의 일부를 복제하는 형태의 자료구조
연결리스트(linked list)
큐(queue) / 데크(deque)
5) 꼬리 재귀 (tail recursion in js)
꼬리재귀(return문에서의 연산→for문이 돌아가는 방식)
참조사이트
- 꼬리재귀는 reduce의 원리와 동일한가?
function repeatString(num,acc){
if ( num === 0 ) {
return acc;}
return repeatString(num-1,acc+num)}작성예정
6) 하노이의 탑 재귀 (js tower of hanoi in recursion)
7) 조합 재귀함수 (js combination in recursion)
참조사이트
기타 재귀함수 예시
//recursion-print-array in javascript
var recursive_function = function(array){
if(array.length === 0){
return [];
}
return array[0] + "\n" + recursive_function(array.slice(1))
}
recursive_function(['1','2','3']);
> "1
2
3
"
// shift로도 가능하다
var recursive_function = function(array){
if(array.length === 0){
return [];
}
return array.shift() + "\n" + recursive_function(array)
}
// 다른방법
var recursive_function = function(array){
if(array.length === 0){
return [];
}
console.log(array.shift());
if(array.length !==0){
recursive_function(array)
}
}참조사이트
차곡차곡 쌓아가는 나의 개발 기록