🔸 재귀는 원래의 자리로 되돌아가거나 되돌아온다는 뜻.
🔸 자기 자신을 호출하는 함수를 재귀 함수라고 함.
function recursion() {
console.log('hello');
recursion();
} // `recursion` 함수를 호출하면 무한 루프 발생
🔸 반복적인 작업을 해야하는 문제를 좀 더 간결하게 작성할 수 있음
문제를 동일한 방식으로 작게 쪼개기 : recursive case
문제를 더이상 안 쪼개지는 가장 작은 단위로 쪼개기 : base case
문제 해결하기 : base case 해결하기
/* 배열의 합을 구할 때 [1, 2, 3]의 합을 구하는 것보다
[2, 3]의 합을 구하는 것이 더 작은 문제 ... */
arrSum([1, 2, 3]) === 1 + arrSum([2, 3])
arrSum([2,3]) === 2 + arrSum([3])
// 위에서 문제를 쪼갠 방식을 반복해서 문제를 쪼개면 더이상 쪼갤 수 없는 상태 도달
arrSum([1,2,3]) === 1 + arrSum([2,3])
arrSum([2,3]) === 2 + arrSum([3])
arrSum([3]) === 3 + arrSum([])
/* 문제를 쪼갤 때 같은 방식으로 쪼갰기 때문에
가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결 가능 */
arrSum([]) === 0 // 문제가 더는 작아지지 않는 순간
arrSum([3]) === 3 + arrSum([]) === 3 + 0 === 3
arrSum([2,3]) === 2 + arrSum([3]) === 2 + 3 === 5
arrSum([1,2,3]) === 1 + arrSum([2,3]) === 1 + 5 === 6
🔸 위의 단계를 반영해 자연수로 이루어진 배열을 입력받고, 배열의 합을 리턴하는 함수 arrSum
작성.
function arrSum (arr) {
// 빈 배열을 입력 받았을 때 0을 리턴하는 조건문
// 가장 작은 문제를 해결하는 코드, 재귀를 멈추는 코드
if(arr.length === 0) {
return 0
}
// 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
// 재귀(자기 자신 호출)를 통해 문제를 작게 쪼개나가는 코드
return arr.shift() + arrSum(arr)
🔸 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
🔸 중첩된 반복문이 많거나 반복문의 중첩횟수를 예측하기 어려운 경우
🔸 문제를 가장 단순하게 정의
arrSum
의 경우 number
타입의 요소로 갖는 배열을 입력받고, number
타입을 리턴srrSum: [number] => number
입출력값 정의🔸 문제를 어떻게 쪼갤 것인지 기준을 정함.
🔸 입력값이나 문제의 순서와 크기로 경우의 수를 나눔.
arrSum
은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있음.arrSum: [number] => number
arrSum([ ])
입력값이 빈 배열인 경우arrSum([요소1, 요소2, ... , 요소n])
그렇지 않은 경우🔸 문제를 더 이상 쪼갤 수 없는 경우 재귀의 탈출 조건을 구성.
🔸 재귀의 기초 (base case) : 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성
탈출 조건이 없는 경우, 재귀 함수는 끝없이 자기 자신을 호출하여 무한 루프에 빠짐.
함수 arrSum
을 더이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([])
의 리턴값은 0.
arrSum: [number] => number
arrSum([ ]) === 0
입력값이 빈 배열인 경우 : "해결"arrSum([요소1, 요소2, ... , 요소n])
🔸 남아있는 복잡한 문제 해결
arrSum
에 입력된 경우, 입력된 배열을 배열의 첫 요소와 나머지 요소를 입력값으로 갖는 문제로 쪼개고, 둘을 더함.arrSum: [number] => number
arrSum([ ]) === 0
arrSum([요소1, 요소2, ... , 요소n])
그렇지 않은 경우 : "해결"arrSum
을 재귀적으로 구현 가능.function arrSum(arr) {
// 📍 base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
if (arr의 길이가 0인 경우) {
return 0; // 단순한 문제의 해답;
}
// 📍 recursive case : 그렇지 않은 경우
return 요소1 + arrSum([요소2, ... , 요소n]); // 더 작은 문제로 새롭게 정의된 문제
}