재귀란?
- 문제를 해결할 때 구조가 동일하다면 더 작은 경우를 해결함으로 문제를 해결하는 방법을 말한다.
function arrSum(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
0. 위 예시 함수를 쪼개서 생각해보자.
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);
arrSum([]) = 0;
1. 원래 문제에서 출발 -> 더 작은 경우를 생각한다.
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]);
2. 더는 작아지지 않을때까지 더 작은 경우를 생각해보자.
um([3, 6, 2]) = 3 + arrSum([6, 2]);
arrSum([6, 2]) = 6 + arrSum([2]);
arrSum([2]) = 2 + arrSum([]);
3. 문제가 간단해져서 바로 풀 수 있게 되는 순간에 문제를 차근차근 해결한다.
arrSum([]) = 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
arrSum([2]) = 2 + arrSum([]) = 2;
arrSum([6, 2]) = 6 + arrSum([2]) = 6 + 2 = 8;
arrSum([3, 6, 2]) = 3 + arrSum([6, 2]) = 3 + 8 = 11;
arrSum([10, 3, 6, 2]) = 10 + arrSum([3, 6, 2]) = 10 + 11 = 21;
4. arrSum을 더 엄밀하게 정의할 수 있다.
arrSum(arr)
1. arr이 빈 배열인 경우 = 0
2. 그 외의 경우 = arr[0] + arrSum(첫 요소를 제외한 나머지 배열)
5. 재귀는 언제 사용할까?
재귀적 사고 연습하기
1. 재귀 함수의 입력값과 출력값 정의해보기!
arrSum: [number] => number
2. 문제를 쪼개고, 경우의 수를 나누기
2.1 arrSum은 배열의 크기에 따라 구분 가능!
arrSum([1, 2, 3, 4])과 arrSum([2, 3, 4])을 구하는 방법은 동일하니까 이 구분은 적절하다고 판단된다.
2.2 경우의 수로 나눈다!
빈배열인 경우, 그렇지 않은 경우로 나눌 수 있다.
arrSum: [number] => number
arrSum([ ])
arrSum([el, e2, ... , en])
3. 단순한 문제 해결하기
2번처럼 문제를 순서나 크기로 쪼개면서 가장 쉬운 문제를 먼저 해결한다. 이를 재귀으 기초(base case)라고 부른다. 그리고 재귀의 기초는 재귀함수구현 시 재귀의 탈출조건(재귀 호출이 멈추는 조건)을 구성하게 된다.
arrSum: [number] => number
arrSum([ ])
arrSum([el, e2, ... , en])
4. 복잡한 문제 해결하기
arrSum: [number] => number
arrSum([ ]) = 0
//위에는 입출력 단순히 표시하고
//빈배열일때 다음으로 이제 본격적으로 재귀 시작!(아래)
arrSum([e1, e2, ... , en]) = e1 + arrSum([e2, ..., en])
배열이 있을때(head)와 나머지 부분(tail)로 구분하자. 그럼 arrSum을 해결할 수 있다.
5. 코드 구현하기
function arrSum(arr) {
//재귀의 기초(base case)
//문제를 더 이상 쪼갤 수 없는 경우
if (arr의 길이가 0인 경우) {
return 0;
}
// recursive Case
// 그렇지 않은 경우
// head : 배열의 첫 요소
// tail : 배열의 첫 요소만 제거된 배열
return head + arrSum(tail);
}
추가적으로 일반적인 재귀함수의 템플릿(재귀함수연습에 활용해보자!)
function recursive(input1, input2, ...) {
// 재귀의 기초 (base case)
if (문제를 더 이상 쪼갤 수 없을 경우) {
return 단순한 문제의 해답;
}
// recursive Case
// 그렇지 않은 경우
return 더 작은 문제로 새롭게 정의된 문제
// 예1. 어떤값 + 본인함수(x,y,z, ...)
// 예2. 어떤값 * 본인함수(x,y,z, ...)
}