What is Recursion?

함수를 스스로 호출하여 반복하는 것을 말한다.
기본적으로 반복문의 형태를 띄고 있기 때문에 반드시 탈출 조건이 있어야 한다.
그렇지 않으면 무한 루프롤 돌게 된다

겁나게 어려웠던 문제

그것은 바로 unpackGiftbox.. 한번 다시 리뷰해보도록 하자

문제
선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아 조건에 맞는 선물이 있는지 여부를 리턴해야 합니다

입력

인자 1 : giftbox

• 문자열, 배열을 요소로 갖는 재귀적으로 정의된 배열
• 문자열은 선물 상자에 들어있는 각 선물의 이름을 의미합니다.
• 배열은 더 작은 선물 상자를 의미합니다.

인자 2 : wish
string타입의 문자열

출력
boolean타입을 리턴해야 합니다

주의사항

• 함수 unpackGiftbox는 재귀함수의 형태로 작성합니다. (당연)
• 반복문 사용이 가능합니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다.(immutability)
• 빈 배열 또는 빈 문자열을 입력받은 경우, false를 리턴해야 합니다.

입출력 예시

const giftBox = ['macbook', 'mugcup', ['eyephone', 'postcard'], 'money'];

let output = unpackGiftbox(giftBox, 'iphone');
console.log(output); // --> false

output = unpackGiftbox(giftBox, 'postcard');
console.log(output); // --> true

my code is..

function unpackGiftbox(giftBox, wish) {

    for (let i=0; i<giftBox.length; i++){
      if(giftBox[i] === wish){
        return true;
      }
      if(Array.isArray(giftBox[i]) === true){
        const result = unpackGiftbox(giftBox[i], wish);
        
        if (result === true){
          return true;
        }
        
      }
   
    }
  return false;
}

먼저, 입출력 예시를 보면 giftbox 배열 안에 또 다른 giftbox를 담아 두는 만행을 저질러 두었다. 그래서 이건 무조건 반복문으로 검사해야 하는 일이다.

반복문의 반복 회수는 큰 응용 없이 기본 공식대로 작성하고, 반복문 안에서 조건을 작성할 때 주의해야 한다.
내가 풀었던 방법의 핵심 포인트는 아래와 같다.

1. giftbox 배열의 i번째 요소가 wish로 받은 문자열(인자 2)과 동일하다면
   true를 리턴하고 반복문을 종료한다. (첫 번째 탈출 포인트)

2. giftbox 배열의 i번째 요소가 '배열'일 경우 그 배열을 열고 1을 반복한다.
 2-1. 1을 반복하다가 true가 나오면 결과로 true를 리턴하고 반복문을 종료한다 (두 번째 탈출 포인트)
 
3. 그 외의 모든 상황에서 false를 리턴한다.

2번째 절차에서 배열인지 확인하려면 Array.isArray를 이용하여 giftbox의 i번째 요소를 검사하도록 한다. typeof에서는 배열 확인이 불가능하기 때문!

이게 풀고 나서 다시 보면 진짜 절대 어려운 문제가 아닌데 풀 때는 겁나게 어려웠다.
재귀함수가 어렵게 느껴졌던 이유는 재귀함수를 어디서 발동시켜야 하는 지 감이 오지 않기 때문이다
재귀함수를 써야 할 때는 수도코드를 이용하여 로직을 짠 뒤 반복 작업이 반드시 꼭 필요해 보이는 최소한의 위치에서 쓴다고 생각해야 편하다.

Reference

이거 근데 풀고 나서 보니까 내가 푼게 레퍼런스 코드랑 거의 일치한다.
2가지 다른 방법으로 풀 수 있는 코드가 있어서 그 코드들과 비교해 보도록 한다.

풀이 방법 1

function unpackGiftbox(giftBox, wish) {
  let anotherBoxes = [];
  for (let i = 0; i < giftBox.length; i++) {
    if (giftBox[i] === wish) {
     return true;
   } else if (Array.isArray(giftBox[i])) {
     anotherBoxes = anotherBoxes.concat(giftBox[i]);
    }
  }
  if (anotherBoxes.length > 0) {
    return unpackGiftbox(anotherBoxes, wish);
  }
   return false;
 }

풀이 방법 2

 function unpackGiftbox(giftBox, wish) {
   const result = giftBox.reduce((acc, curr) => {
     if (curr === wish) {
       return true;
     } else if (Array.isArray(curr)) {
       return unpackGiftbox(curr, wish) || acc;
     } else {
       return acc;
     }
   }, false);
   return result;
 }