[Day 42] 2022-0822 : 재귀함수2 (재귀 지옥...)

🐈오늘 공부한 것

✔️재귀함수 복습

재귀함수에 대한 이해가 부족하여 풀었던 문제를 다시 복습했다.

라이브세션에서 재귀 함수에 대해 강의해주셨던 부분은 아래와 같다.

1. 문제를 동일한 방식으로 쪼갠다. => recursive case
2. 더 이상 쪼개지지 않을 때 그 상태가 재귀의 탈출 조건이 된다. => base case
3. base case 를 해결하면 쪼개졌던 문제를 한번에 해결할 수 있다.

재귀 함수를 푸는 이상적인 방법인데, base case를 간단하게 도출할 수 있거나 재귀 호출 방법을 쉽게 파악할 수 있으면 괜찮지만, 재귀를 호출하는 조건이 복잡해지면 엄청 어렵게 느껴진다. 

특히 이진 트리나 그래프를 탐색할 때 식을 어떻게 짜야 재귀 호출로 문제를 풀 수 있는지.. 감이 전혀 오지 않고 풀이를 봐도 그림을 그려야 겨우 이해가 된다. ^^;;

그래서 문제를 복습해 보았다. 

[ 순서가 뒤집힌 배열 만들기 ]

function reverseArr(arr) {
  // 종료 조건
  if (arr.length === 0) return [];

  const head = arr[0];
  const tail = arr.slice(1);
  console.log(head, tail);
  return [...reverseArr(tail), head];

  // 재귀 조건
  // reverseArr([1,2,3]) => [3] + reverseArr([1,2]) => [3,2] + reverseArr([1])
  // => reverseArr([]) ==> return;
}

먼저 이 문제는 비교적 간단하게 recursive case와 base case를 판단할 수 있었다. 첫 함수 호출에서 재귀적으로 반복 호출하면서 배열의 일부분을 별도로 분리하고, 함수가 끝나면서 순차적으로 리턴이 될 때 저장해둔 배열 일부분과 합쳐 순서가 뒤집힌 배열 혹은 합계 등 다양하게 만들 수 있다. 

이 재귀 함수의 동작 과정을 그림으로 보면 아래와 같다.

tail로 분리했던 부분이 head로 넘어가고, head가 다시 tail이 되어 리턴된다. 기존에 head로 분리했던 부분이 tail과 순서가 바뀐 대로 병합되어 배열이 되기 때문에 정답이 된다.

 

이외에 더 어려운 재귀 문제들도 많은데, 나중에 알고리즘 공부를 할 때 더 자세히 파고들기로...

✔️JSON.stringify 직접 구현

첫 번째 과제는 JSON.stringify 함수를 재귀를 사용해 직접 구현하는 과제였다. 예전에 JSON 직렬화 함수가 재귀적인 방식으로 동작한다고 들은 것 같은데 실제로 구현해보니 나에게는 상당히 어려웠다.

테스트케이스로 주어진 객체에 대해서 JSON.stringify와 동일한 동작을 하는 함수를 구현한다. 먼저 JSON.stringify는 문자열 요소에 대해서 쌍따옴표를 추가하고, 나머지 타입은 문자열로 변경한다. 배열화 하는 부분도 어려웠지만, 더 어려웠던 부분은 객체를 반복해서 재귀를 호출하는 부분이었다. 처음 접근은 배열이나 객체나 typeof obj === 'object' 로 확인해서 한번에 파고들어야겠다고 생각했는데, 잘못된 생각이었다. 문자열화를 할 때 배열이냐 객체이냐에 따라서 분기를 다르게 해주어야 하고, 배열 혹은 객체를 만났을 경우 괄호부터 파고들어 문자열로 변경하는게 아니라 타입에 따라 변경된 결과물에 [] 혹은 {} 괄호를 씌워서 문자열화 한다고 생각하면 쉽다. 

// 배열
if (Array.isArray(obj)) {
    let result = '';
    for (let el of obj) {
      result += stringifyJSON(el) + ',';
    }
    result = result.slice(0, -1);
    return `[${result}]`;
  }
  
 // 객체
if (typeof obj === 'object') {
let result = '';
for (let key in obj) {
  if (typeof obj[key] === 'function' || obj[key] === undefined) {
    continue;
  }
  result += `${stringifyJSON(key)}:${stringifyJSON(obj[key])},`;
}
result = result.slice(0, -1);
return `{${result}}`;
}

인자로 받고있는 obj가 배열일 경우 처음 만난 if문 조건에 해당되어 다음 if문으로 넘어가지 않는다. 따라서 하단 객체 부분에는 객체 타입 obj만 해당된다. key로 객체를 순회하면서 함수나 undefined는 stringify 함수를 적용하지 않는다는 조건에 따라 continue로 건너뛰고, 그 나머지만 key와 value로 접근하여 문자열화를 한 뒤 { } 중괄호에 담아 다시 문자열화 하면 된다. 

문제를 풀 때 한 번에 다 해결할 수 있는 방법을 찾느라 고민하기 보다는, 일단 합리적인 선에서 코드를 짜는 것도 좋은 것 같다. 매번 아 어떻게 한 번에 다 해결할 수 있지? 생각하느라 기능 구현에서 멀어지는 것 같다. 

✔️Tree UI 과제 

이 과제는 재귀적으로 구성된 데이터를 리스트로 구성해 각 단계에 맞게 화면에 출력해주는 과제였다. 함수에 menu와 currentNode가 주어지면 해당 menu 정보를 가지고 ul과 li를 구성하고, 다음 재귀 호출에 menu.children 배열과 ul을 넘겨주면 해당 ul에 하위 정보로 만든 li가 append된다. 재귀를 반복하다가, children이 더 이상 존재하지 않으면 다음 재귀를 호출하지 않고 종료되는 함수이다. 여기서 recursive case와 base case를 도출할 수 있는데, base case는 children 에 해당하는 하위 배열이 없을 경우이고, 재귀 조건은 그 외, children이 존재하는 경우가 될 것이다. 

이 함수의 동작 방식을 생각해보면...

1. 먼저 menu는 배열이기 때문에 menu 하나에 대해 접근하기 위해 for문으로 반복한다.

2. 반복중인 el 에 대해서 li를 만들것이기 때문에 조건문 바깥에 li를 생성한다.

3. 조건에서는 el에 하위 배열 포함 여부를 확인한다. 하위 배열이 존재하지 않는다면 li에 이름만 추가해주면 되고, 하위 배열을 포함한다면, 앞서 만든 li에 데이터를 추가하고, 하위 배열과 ul을 넘겨 이 함수를 반복호출해준다. 

4. 결과적으로 반복이 종료되면 currentNode로 받아온 상위 ul에 현재 li가 append된다.

코드는 아래와 같다.

function createTreeView(menu, currentNode) {
  for (let el of menu) {
    let liElement = document.createElement('li');

    if (!el.children) {
      liElement.textContent = el.name;
    } else {
      let inputElement = document.createElement('input');
      let spanElement = document.createElement('span');
      let ulElement = document.createElement('ul');

      inputElement.type = 'checkbox';
      spanElement.textContent = el.name;

      liElement.append(inputElement, spanElement, ulElement);

      createTreeView(el.children, ulElement);
    }
    currentNode.append(liElement);
  }
}

🐈더 공부할 것

1. 웹브라우저 렌더링 과정

2. 리액트 훅

🐈오늘의 느낀 점

1.컨디션 조절에 실패해서 어제 TIL을 다음날 아침에 작성하고 있다. 재귀 함수를 공부하면서 약간 멘붕이 와서 집중력도 흐려졌는데, 이해가 되는 선까지 최대한 접근해 보았다. 위에서도 말한 바와 같이 재귀적으로 풀어야하는 문제를 보면 접근을 어떻게 해야하는지 의사코드 작성도 힘든 것 같다. 그래도 무작정 코드를 짜는 것 보다는 어느정도 로직을 생각하고 짜는게 맞는 것 같다.