[TIL] #22. 재귀

2022.6.23. (목)

1. 오늘의 소감

• 오늘은 재귀(recursion) 에 대해 배웠다. 사실 이전 부터 재귀가 무엇인지는 알고 있었지만, 재귀 문제를 푸는 방법은 몰랐다. 그래서 늘 막막했는데, 이번 학습 콘텐츠에서는 재귀 푸는 방법이 자세하게 설명되어있어서 재귀 문제에 조금씩 자신감이 생기는 중이다.
• 재귀 문제는 처음 보면 너무 막막하다. 이걸 어떻게 풀어야되지 싶고… 하지만 오늘 배운대로 차근차근 base case 와 recursive case 를 나눠서 생각해보면… 신기하게도 문제가 풀린다! 물론 가끔은 공식만 적용해서 풀어서 머리가 풀이를 못따라가느라 ‘어? 어떻게 풀린거지?’ 라는 생각이 들 때도 있긴하지만🥲, 그래도 재귀 문제만큼 풀렸을 때 쾌감이 짜릿한 문제도 없는 듯하다!
• 코플릿 14번 문제는 많이 헤맸다… 최소 한 시간은 걸린 듯하다😇

2. 학습한 키워드

• 재귀, base case, recursive case, 탈출 조건, 입력값 & 출력값 정리하기, 재귀 함수를 활용하는 방식으로 문제 쪼개기, 문제를 비슷한 구조의 더 작은 문제로 쪼갤 수 있을 때 & 반복문이 많거나 반복문 중첩 횟수를 알 수 없을 때 재귀를 활용한다.

3. 키워드를 바탕으로 학습 내용 설명해보기

• 재귀 함수는 자기자신을 호출하는 함수이다.
• 재귀함수는 보통 1) 문제를 비슷한 구조의 더 작은 문제로 쪼갤 수 있을 때, 2) 반복문이 많거나 중첩 횟수를 예측할 수 없을 때 활용하기 좋다.
• 재귀 문제 푸는 방법
  1. 입력값과 출력값을 정리한다.
  2. 문제를 동일한 방식(재귀함수를 활용하는 방식)으로 쪼개본다. → 이 쪼개는 방식이 recursive case다.
  3. 문제를 더 이상 쪼갤 수 없는 케이스(= 리턴 값이 명확한 케이스) 를 구한다. → 이게 base case = 탈출 조건이 된다!
  4. base case 를 푼다.
• 일반적인 재귀 템플릿

function recursion(input1, input2, ... ) {
    //base case = 리턴값이 명확한 케이스
    // 탈출 조건
    if(문제를 더 이상 쪼갤 수 없는 경우) {
        return 단순한 문제의 답;
    }

    //recursive case : 그렇지 않은 경우
    return 더 작은 문제로 새롭게 정의된 문제
    // 보통 recursion(...) 의 전달인자 값이 달라지면서
    // 문제가 더 작게 쪼개진다.
}

• 보통 위쪽에 base case로 리턴을 바로 해줄 수 있는 조건을 걸어주고, 이 조건에 걸리지 않는 경우에는 아래쪽에서 recursive case로 문제를 작게 쪼개주는 방식으로 쓴다.
• 다만 이 템플릿에 너무 의존하지는 말자! 리턴문에 꼭 재귀함수가 들어가지는 않는다! → 아래 14번 예시 참고… 이 문제는 억지로 템플릿처럼 생각하다가 더 꼬였다…ㅠ
• 코플릿 재귀 14번 <unpackGiftbox 문제> = 다중 중첩 배열 푸는 문제
  • 다차원 배열에서 wish 와 동일한 요소가 있으면 true 없으면 false

function unpackGiftbox(giftBox, wish) {
    for(let gift of giftBox) {
        //base case : wish 인 요소가 존재할 때
        if(gift === wish) return true;

        //recursive case : 요소가 배열일 때
        if(Array.isArray(gift)){
            if(unpackGiftbox(gift, wish) === true) return true;
        }
    }

    //base case : for문을 다 검사하고 나와도 wish가 없을 때
    return false;
}