Week 4-2 : 재귀적으로 생각하기

---

TIL List

• 재귀적으로 해결하기

• 배열 안의 배열에 접근하는 방법

---

1) 재귀 함수 문제 해결 과정

1. 객체 안의 객체에 접근하기

러시아 전통인형 마트료시카에 대한 정보를 담은 객체와 수를 입력받아 조건에 맞는 인형이 있는지 여부 (Boolean 값) 를 리턴해야 한다.

입력받을 객체의 형태는 다음과 같다.

const matryoshka = {
  size: 10,
  matryoshka: {
    size: 9,
    matryoshka: null,
  },
};

let output = findMatryoshka(matryoshka, 10);
console.log(output); // --> true

자, 이제 이 문제를 위에서 배운 재귀적 사고 를 통해 하나씩 하나씩 접근해보자.

1. 입력받을 매개변수는 matryoshka, size 두 개이다.

2. 입력받은 size 와 해당 matryoshka 의 size 가 일치할 때 true 를 리턴한다.

3. 일치하지 않을 경우 재귀 함수를 통해 다음 matryoshka 로 넘어가고, 2번을 실행한다.

4. 만약, 해당 matryoshka 의 value 가 null 이면 false 를 리턴한다.

이를 바탕으로 코드를 짜보면 다음과 같다.

function findMatryoshka(matryoshka, size) {
  if (matryoshka.size === size) { // 탈출 조건
    return true;
  } else {
    return findMatryoshka(matryoshka.matryoshka, size);
  }
  return false; // 탈출 조건 2 (최종적으로 원하는 값이 없으면 false 를 리턴한다.)
}

과연 이 코드는 잘 짜여있다고 볼 수 있을까?

위 코드의 문제점은 아래의 상황일 때 발생한다.

const matryoshka = { size: 10, matryoshka: { size: 3, matryoshka: null }}
const size = 7

findMatryoshka(matryoshka, size) // Cannot read property 'size' of null

에러 코드는 "size 의 값으로 null 이 들어왔을 때 나는 이 값을 읽을 수 없다." 라고 말하고 있다.

그렇다면 우리는 조건을 다음과 같이 바꿔야 할 것이다.

1. 입력받을 매개변수는 matryoshka, size 두 개이다.

2. 입력받은 size 와 matryoshka 의 size 가 일치할 때 true 를 리턴한다.

3. 일치하지 않을 경우 다음 matryoshka 의 객체의 value 값을 확인한다. 이 때 value 값이 null 이면
   false 를 리턴한다.

4. null 이 아니라면 재귀 함수를 통해 다음 객체로 넘어가고, 2번을 진행한다.

수정한 조건을 바탕으로 다시 코드를 짜보자.

function findMatryoshka(matryoshka, size) {
  if (matryoshka.size === size) { // 탈출 조건
    return true;
  } else if (matryoshka.matryoshka) { // 해당 값이 null 이면 false 이므로 if 문이 실행되지 않는다.
    return findMatryoshka(matryoshka.matryoshka, size)
  }
  return false; // 탈출 조건 2 (최종적으로 원하는 값이 없으면 false 를 리턴한다.)
}

const matryoshka = { size: 10, matryoshka: { size: 3, matryoshka: null }}
const size = 7

findMatryoshka(matryoshka, size) // false;

재귀 함수를 통해 if (matryoshka.size === size) {return true;} 가 실행되기 전에 다음 마트료시카의 값이 true 인지 먼저 검사를 하게 했고, 이렇게 하니 원하는 값이 나오게 됐다.

---

2. 배열 안의 배열에 접근하기

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

입력받을 배열의 형태는 다음과 같다.

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

unpackGiftbox(giftBox, 'postcard'); // --> true

마찬가지로 재귀적 사고 를 통해 문제를 하나씩 하나씩 접근해보자.

1. 반복문을 사용해 배열의 요소를 하나하나 찾는다.

2. 만약, 배열안에 배열이 있을 경우 재귀 함수를 통해 해당 배열을 검사한 뒤 검사가 끝나면 다음 요소로 넘어간다.

3 만약 입력 받은 배열에 wish 값이 있다면 (giftBox === wish ('postcard')) true 를 리턴한다.

4 만약 wish 값이 없다면 false 를 리턴한다.
 

처음 내가 풀었던 방법은 다음과 같다.

function unpackGiftbox(giftBox, wish) {

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

기본적으로 배열안의 요소를 돌면서 wish 와 같다면 바로 true를, 배열안의 요소를 다 돌아도 wish 와 같지 않다면 false 를 리턴하도록 했다.

그리고 배열의 요소의 타입이 Array 일 경우 재귀 함수를 통해 해당 giftBox[i] 를 다시 검사하도록 했다.

하지만 위의 코드는 한 가지 문제점이 있었는데

const giftBox = ['pen', ['chocopie', ['kimchi', [], 'airpods']]]
const wish = 'airpods'

위와 같이 입력받았을 때 true 를 리턴해야 하지만 false 를 리턴했다.

왜 false 가 나오는지 디버깅을 통해 확인해본 결과 빈 배열을 입력 받았을 때 if 문이 모두 실행이 되지 않고 바로 return false 를 하는 모습이다. 따라서 다음 요소인 'airpods' 까지 반복문이 돌지 못한채 끝나게 돼서 false 가 나오게 된 것이었다.

따라서 나는 재귀 함수의 값을 변수에다가 따로 저장한 뒤, 변수에 할당된 해당 배열의 값 중 true 가 있다면 return true 를 하는 식을 추가해줬다.

function unpackGiftbox(giftBox, wish) {

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

이렇게 하게 되면 빈 배열에 입력했을 때 giftBox.length 는 0 이므로 for 문은 돌지 않게 되고 return false 를 통해 result = false 가 되므로 빈 배열은 false 인 상태에서 다음 요소로 접근할 수 있게 된다.