[JS]재귀함수 예제1

기본적인 재귀함수는 전에 풀어보았다. 오늘은 좀 더 복잡한 재귀함수 코플릿에 도전해본다!

 

Q1.

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

<입출력예시>

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

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

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

<내코드> - 실패

function unpackGiftbox(giftBox, wish) {
  if (giftBox.length === 0 || wish.length === 0 && giftBox !== []){return false}
  const head = giftBox[0]
  const tail = giftBox.slice(1)
  if (wish === head){return true}
  else if (typeof head === 'object') {unpackGiftbox(head, wish)}
  else if (typeof head === 'string') {unpackGiftbox(tail, wish)}

  return false
}

<어려웠던 점>

• [] 배열이 입력으로 들어왔을 경우, false를 출력하는 대신 다음으로 넘어가고 싶었는데, 뜻대로 안됨.
• head의 타입에 따라 각각 head, tail을 재귀적으로 호출하게 했는데, 그렇다면 head 배열 뒤에 있는 값들은 소실됨.

<해결1>

function unpackGiftbox(giftBox, wish) {
  // recursive
  for (let i = 0; i < giftBox.length; i ++){
    if (giftBox[i] === wish){return true} // for문을 돌면서 giftBox[i]와 wish가 일치하는지 판단하고, 일치한다면 true를 리턴한다.
    else if (Array.isArray(giftBox[i]) && giftBox[i].length !== 0){ // 만약 giftBox[i]가 배열이라면, 함수를 재귀적으로 호출한다.
      const result = unpackGiftbox(giftBox[i], wish)
      if (result === true) {return true} // 배열 내에서 일치한 것이 발견되면 바로 true를 리턴할 수 있도록 한다.
    }
  }

  return false // for문을 다 돌았을때 true가 없다면, false를 리턴한다.
}

찾은 값이 배열인 경우, 재귀호출을 통해 해당 배열 내에 wish와 일치한 값이 있는지 판단하려 했는데, 모든 함수를 돌고 결국 false를 출력하므로, 아무리 재귀호출을 써도 결과값은 false였다. 그래서 재귀호출한 값을 변수에 할당하고 그 값이 true이면 곧장 함수를 끝내도록 true를 리턴하도록 했다.

<레퍼런스>

 function unpackGiftbox(giftBox, wish) {
   // recursive case
   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);
   }
   
   // base case
   return false;
}

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;
 }