재귀함수란 무엇일까??
가장 간단하게 축약하자면 자기자신 즉, 함수 스스로를 호출하면서 내부적으로 작업을 수행하게끔 하는 것이다.
그렇다면 재귀는 어떠한 상황에서 효율적일까??
Section2 에서는 재귀를 사용하기 좋은 상황에 대해, 다음과 같이 설명을 하고있다.
1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(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);
}
}
}
}
}
}
}
}
이른바 속칭 아도겐이라고도 부르기도 하는 식의 for문의 중첩인데,
이러한 상황도 재귀적으로 코드를 작성하면 간단하게 표현을 할 수 있을 것이다.
그렇다면 재귀함수를 작성하는데에 있어서 어떤 알고리즘으로 진행을 해야 할까??
1. 재귀 함수의 입력값과 출력값 정의하기
재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 됩니다. 재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의하는 것입니다. 함수 arrSum의 경우 number 타입을 요소로 갖는 배열을 입력으로 받고, number 타입을 리턴합니다. 이를 좀 더 간단하게 표기하면 다음과 같습니다.
arrSum: [number] => number2. 문제를 쪼개고 경우의 수를 나누기
주어진 문제를 어떻게 쪼갤 것인지 고민합니다. 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인합니다. 일반적인 경우, 입력값으로 이 기준을 정합니다. 이때 중요한 관점은 입력값이나 문제의 순서와 크기입니다. 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 됩니다. 그리고 구분된 문제를 푸는 방식이 순서나 크기에 관계없이 모두 같다면, 문제를 제대로 구분한 것입니다.
함수 arrSum 의 경우 입력값인 리스트(배열)의 크기에 따라, 더 작은 문제로 나눌 수 있습니다. 그리고 arrSum([1, 2, 3, 4]) 를 구하는 방법과 arrSum([2, 3, 4]) 을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있습니다.
이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눕니다. 일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눕니다.
함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있습니다. 각각의 경우는 다른 방식으로 처리해야 합니다.
arrSum: [number] => number
arrSum([ ])
arrSum([e1, e2, ... , en])
3. 단순한 문제 해결하기
문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결합니다. 이를 재귀의 기초(base case)이라고 부릅니다. 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성합니다.
함수 arrSum 을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum([]) 의 리턴값은 0입니다.
arrSum: [number] => number
arrSum([ ]) = 0
arrSum([e1, e2, ... , en])
4. 복잡한 문제 해결하기
남아있는 복잡한 경우를 해결합니다.
길이가 1 이상인 배열이 함수 arrSum 에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고(배열의 맨 앞의 요소이기 때문에 head라고 이름 붙이겠습니다.), 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이를 해결하여 얻은 결과를 head에 더합니다.
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);
}
와 같은식으로 codeState 에서는 유어클래스가 정리되어있다.
그리고 오늘은 재귀함수와 관련된 코플릿을 풀어봤는데, 그중에서 풀기 까다로웠으며 이해가 잘 안됬던 문제 하나를 가져와 본다.
입출력 예시
const matryoshka = {
size: 10,
matryoshka: {
size: 9,
matryoshka: null,
},
};
let output = findMatryoshka(matryoshka, 10);
console.log(output); // --> true
output = findMatryoshka(matryoshka, 8);
console.log(output); // --> false
위와 같은 출력결과가 나오도록 코드를 작성하는 문제였는데, 이 문제를 풀 때에 참 고민을 많이 했다. 결국에는 풀긴 했지만, React 에서 많이 쓰이는 삼항연산자를 이용해서 재귀함수를 작성하는 방식까지 적용해 보았다.
첫번째, 기존의 재귀함수 작성법 (내가 알던 지식)
function findMatryoshka(matryoshka, size) {
// recursive case
if (matryoshka.size === size) {
return true;
} else if (matryoshka.matryoshka && matryoshka.size > size) {
return findMatryoshka(matryoshka.matryoshka, size);
}
// base case
return false;
}
그리고 다음이 삼항연산자를 이용해서 간략하게 작성한 코드이다
두번째, 새롭게 연습중인 삼항연산자를 이용한 코드
function findMatryoshka(matryoshka, size) {
if(matryoshka.size === size) return true;
return matryoshka.matryoshka ? findMatryoshka(matryoshka.matryoshka, size) : false;
}
특히나 삼항연산자를 사용해서 코드를 작성하는 방식에 아직 길들여지지 않아서 골머리를 앓았던 문제였다.
이해가 안되는 부분은 항상 TIL 을 작성하고, 다시 골머리를 앓아봐야겠다.
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
PS. 오늘부터 코딩테스트를 위한 toy 문제를 풀기 시작했는데... 1번 문제부터 막혔다.
레퍼런스 코드를 봐도 이해가 잘되지않는다... 다시금 보면서 이해를 해야겠지...
미라클 모닝을 시작한김에 다시한번 toy 문제나 노려보러 가야겠다
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
