🔎 드디어 코드스테이츠의 섹션 3가 시작되었다.. 섹션 3의 시작은 재귀 함수였는데 개념 자체나 작동 방식이 어려운 것은 아니였으나 실제로 연습 문제를 풀면서 코드를 작성하려고 하니, 재귀적 사고를 하는 것이 아직 어색해서 어려웠다. 내일 학습 전에 다시 정리해보며 복습해보고자 한다.
🔎 1. 재귀 - 기초
재귀란,원래의 자리로 되돌아가거나 되돌아오는 것을 말한다.
//재귀의 코드 예시 function recursion () { console.log("This is") console.log("recursion!") recursion() }
✔️recursion 함수?
recursion 함수를 호출하면,
자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행되는 것을 볼 수 있다.
이 recursion 함수처럼 자기 자신을 호출하는 함수를재귀 함수라고 한다.
✔️ 재귀 함수 왜 사용할까?
재귀 함수를 잘 활용하면,
반복적인 작업을 해야하는 문제를 좀 더간결한 코드로 풀어낼 수 있다.
✔️ 재귀 함수 언제 사용하는 것이 좋을까?
- 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
- 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
- 이 밖에도, 알고리즘 문제의 많은 부분(코딩 테스트, 알고리즘 테스트,직무 면접 등)
for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { for (let k = 0; k < n; k++) { for (let l = 0; l < n; l++) { for (let m = 0; m < n; m++) { for (let n = 0; n < n; n++) { for (let o = 0; o < n; o++) { for (let p = 0; p < n; p++) { // do something someFunc(i, j, k, l, m, n, o, p); } } } } } } } }
🔎 2. 재귀 - 문제 해결
→ 문제: 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 함수 `arrSum` 을 작성하세요. // 배열 [1, 2, 3, 4, 5])
1. 문제를 작게 쪼개기
//합을 구하는 과정을 작게 쪼개기 arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) arrSum([3, 4, 5]) === 3 + arrSum([4,5]) arrSum([4, 5]) === 4 + arrSum([5]) ...
2. 문제를 가장 작은 단위로 쪼개기
//arrSum 이 빈 배열을 받게되면서 문제를 더이상 쪼갤 수 없는 상태 ... arrSum([5]) === 5 + arrSum([])
3. 문제 해결하기
arrSum([]) === 0; // <-- 문제가 더는 작아지지 않는 순간 // 가장 작은 경우의 해결책을 적용합니다. arrSum([5]) === 5 + arrSum([]) === 5 + 0 === 5; arrSum([4, 5]) === 4 + arrSum([5]) === 4 + 5 === 9; arrSum([3, 4, 5]) === 3 + arrSum([4, 5]) === 3 + 9 === 12; arrSum([2, 3, 4, 5]) === 2 + arrSum([3, 4, 5]) === 2 + 12 === 14; arrSum([1, 2, 3, 4, 5]) === 1 + arrSum([2, 3, 4, 5]) === 1 + 14 === 15; //arrSum 함수의 리턴값이 나오면서 연쇄적으로 문제가 해결되고, //최종적으로는 문제 전체가 해결되는 것을 볼 수 있다.
function arrSum (arr) { // 빈 배열을 받았을 때 0을 리턴하는 조건문 // --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드 if (arr.length === 0) { return 0 } // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수 // --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드 return arr.shift() + arrSum(arr) }
🔎 3. 재귀 - 작동 방식
arrSum 함수가 내부에서 arrSum 함수를 호출하면서 문제가 쪼개어져 나가고,
결국 문제를 더이상 쪼갤 수 없는 arrSum([]) 까지 함수가 호출되는 것을 볼 수 있다.
arrSum([]) 는
조건문에 의해 더이상 자기자신을 호출하지 않고, 숫자 0을 리턴하면서 종료.
그 결과 중첩되어있던 함수들도 연쇄적으로 숫자를 리턴하고,
최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.
🔎 3. 재귀 - 재귀적 사고
1. 재귀 함수의 입력값과 출력값 정의하기
재귀적으로 사고하는 데에 가장 먼저 해야 할 일은
문제를가장 추상적으로 또는,가장 단순하게정의하는 것이다.
함수의 입출력값을 정의하는 것은 그 첫 출발점이다.arrSum: [number] => number ← 입출력값 정의
2. 문제를 쪼개고 경우의 수를 나누기
다음으로는 주어진 문제를
어떻게 쪼갤 것인지 고민하기
문제를 쪼갤 기준을 정하고,
정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.
일반적으로, 입력값을 이 기준으로 정한다.
이때 중요한 관점은 입력값이나 문제의 순서와 크기입니다.
주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나,
순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 된다.
그리고 구분된 문제를 푸는 방식이 순서나 크기와 관계없이 모두 같다면,
문제를 제대로 구분한 것이다.//함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다 //각각의 경우는 다른 방식으로 처리해야 한다 arrSum: [number] => number arrSum([ ]) ← 입력값이 빈 배열인 경우 arrSum([요소1, 요소2, ... , 요소n]) ← 그렇지 않은 경우
3. 단순한 문제 해결하기
문제를 여러 경우로 구분한 다음에는,
가장 해결하기 쉬운 문제부터 해결한다. 이를재귀의 기초(base case)라고 부른다.
재귀의 기초는 나중에 재귀 함수를 구현할 때,
재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성합니다.
탈출 조건이 없는 경우
재귀 함수는 끝없이 자기 자신을 호출하게 되고,
그렇다고 문제를 덜 쪼갠 상태에서
탈출 조건을 세우는 경우 문제를 제대로 해결할 수 없게 되므로
문제를 최대한 작게 쪼갠 후에 문제를 해결하는 것이 중요하다.//함수 arrSum 을 더이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, //이때 arrSum([]) 의 리턴값은 0입니다. arrSum: [number] => number arrSum([ ]) === 0 ← 입력값이 빈 배열인 경우 : 해결! arrSum([요소1, 요소2, ... , 요소n])
4. 복잡한 문제 해결하기
남아있는 복잡한 경우를 해결하기
arrSum: [number] => number arrSum([ ]) === 0 arrSum([요소1, 요소2, ... , 요소n]) === 요소1 + arrSum([요소2, ..., 요소n]) ← 그렇지 않은 경우 : 해결! //배열을 첫 요소와 더 작은 문제로 쪼개는 방법만 안다면, //함수 arrSum 을 재귀적으로 구현할 수 있습니다.
5. 코드 구현하기
function arrSum(arr) { // base case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초) if (arr의 길이가 0인 경우) { return 0; } // recursive case : 그렇지 않은 경우 return 요소1 + arrSum([요소2, ... , 요소n]); }// 일반적인 재귀 함수의 템플릿 function recursive(input1, input2, ...) { // base case : 문제를 더 이상 쪼갤 수 없는 경우 if (문제를 더 이상 쪼갤 수 없을 경우) { return 단순한 문제의 해답; } // recursive case : 그렇지 않은 경우 return 더 작은 문제로 새롭게 정의된 문제 }
