TIL: 2022-10-20

⚙️ 오늘 배운 주제

재귀

 

🐹 오늘의 기분

섹션 3가 시작됐다. 오늘부터 데일리 코딩 난이도가 급상승한다고 해서 조금 걱정했다. 풀지 못해도 레퍼런스를 보면서 내 것으로 만들면 된다는 마음가짐으로 임하려고 한다. 그러려고 배우는 거니까!

오늘 데일리 코딩 문제는 전에 코딜리티에서 풀었던 문제랑 똑같아서 푸는데 어려움은 없었다. 워낙 삽질을 많이 했던 문제라 못 풀 수가 없었음 ... 😂 이번 섹션에서는 한 문제를 이틀 간 푼다. 오늘 문제는 다 풀어서 내일은 오늘 페어분과 풀었던 코플릿 문제를 다시 풀어보거나 다른 알고리즘 문제를 풀어봐야겠다. 

재귀는 말은 참 쉬운데 막상 코드로 쓰려니까 머리 터질 것 같았다. 초반 문제까지는 페어분과 함께 조금만 고민해보면 풀 수 있었는데 후반부로 갈수록 더 깊은 고민을 하느라 정적만 맴돌았다. 어찌저찌 다 풀었지만, 완전히 내 것이 되었다는 느낌은 전혀 들지 않아서 몇 번이고 혼자서 다시 풀어봐야 할 듯 하다. 재귀에 익숙해져야 DP나 DFS, BFS 같은 다른 알고리즘 문제 풀 때 고생하지 않을 것 같음. 아자자 🔥

 

🗝 키워드

재귀, base case, recursive case

 

🗣 스스로에게 설명

재귀는 함수 안에서 자기함수를 또 호출하는 것이다.

 

언제 재귀를 써야 하는가?

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우

재귀로 문제 해결하기

수를 입력받으면 0부터 그 수까지의 합을 리턴하는 함수 sumAll을 재귀로 작성하려 한다.
다음과 같은 단계로 문제를 해결할 수 있다.

 

1️⃣ 문제를 가장 단순하게 정의한다. (입력값과 출력값 정의하기)
입력: number 출력: number

 

2️⃣ 문제를 더 이상 쪼개지지 않을 때까지 쪼갠다

문제를 계속 쪼개다 보면 일정 규칙이 보인다.

반복되는 부분을 recursive case로 보내고, 더 이상 쪼개지지 않는 경우를 base case로 다룬다.

base case는 재귀함수의 탈출 조건이다.

여기서는 수가 0이 되는 경우가 base case이다.

base case를 처리하지 않으면 재귀함수가 끝없이 실행된다.

 

3️⃣  복잡한 문제 해결하기

base case를 처리했다면 반복되는 부분을 재귀로 처리한다.

 

function sumAll(num) {
  // base case
  if (num === 0) return 0;
  
  // recursive case
  return sumAll(num - 1) + num;
}

console.log(sumAll(10)); // expected: 55

 

❓ 막히는 or 막혔던 부분

recursive case를 다루는 게 까다로웠다.
특히 원본 배열을 해치지 않도록 immutability를 지키며 작성해야 했는데 이 경우가 정말 헷갈렸다.
역시 연습이 더 필요함을 느꼈다

 

🔍 시도해볼 것

재귀 코플릿 문제 혼자 다시 풀어보고 다른 문제도 다양하게 접해보기 (ex. 하노이의 탑)

재귀는 헷갈리는 만큼 중요한 개념이니 이참에 기초를 단단히 해두자!