재귀함수
재귀함수가 무엇인지는 정보처리 산업기사 자격증 준비때 공부했었기 때문에 개념은 알고있지만... 직접 코드로 작성하려고 하니 손이 떨어지질 않는다.
재귀적으로 사고하기는 너무 어렵다. 살면서 재귀적인 사고를 하면서 산적이 있던가?
술먹고 토하고 술먹고 토하고는 해본 것 같다 ㅋㅋㅋㅋㅋㅋㅋ😭
재귀함수로 구현된 코드는 대부분 for문 while문 등으로 가능하다.
하지만 중첩된 문제를 해결할 때는 재귀함수로 작성하는 것이 훨씬 좋기 때문에... 재귀함수를 무시하고 넘어갈 수는 없다.
재귀함수
: 어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법
재귀적으로 사고하는 법
- 잘게 쪼개어 사고하는 법
- 재귀적 사고
- 함수 자신의 재귀적 호출
- 탈출 조건
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;쪼개서 생각하는 방법
- 원래의 문제에서 출발하여 더 작은 경우를 생각한다
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; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용한다.
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;재귀적으로 사고하기 가이드
1. 재귀 함수의 입력값과 출력값 정의하기
재귀 함수를 통해 어떤 문제를 풀고자 하는 지, 문제를 가장 단순하게 정리.
2. 문제를 쪼개고 경우의 수를 나누기
주어진 문제를 어떻게 쪼갤 것인지 고민한다.
어떤 기준을 정하고 그 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는 지 검토해본다.
일반적으로 입력값이 이 기준을 정하는 대상. 이 때 중요한 관점은 순서와 크기이다.
3. 단순한 문제 해결하기
문제를 여러 경우로 구분한 다음에는 쉬운 문제부터 해결한다.
이를 재귀의 기초(base case)이라고 부른다.
재귀의 기초는 나중에 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성하게 된다.
4. 복잡한 문제 해결하기
남아있는 복잡한 경우를 해결한다.
길이가 1 이상인 배열을 입력으로 받을 경우, 맨 앞의 요소를 따로 구하고(head), 나머지 요소를 새로운 입력값으로 갖는 문제를 해결하여 얻은 결과를 head에 더한다.
배열이 있을 때 head와 나머지 부분(tail)을 구분.
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. someValue + recursive(input1Changed, input2Changed, ...)
// 예2. someValue * recursive(input1Changed, input2Changed, ...)
}