[JS] 재귀 - 상, 중

 

상

 

1. giftBox

 

 

미리 알고 있어야 하는 개념

 

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

// 📌 다른 풀이 방법 1 (추천)

 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]); // anotherBoxs에 새 배열 concat
     }
   }
   if (anotherBoxes.length > 0) {
     return unpackGiftbox(anotherBoxes, wish);
   }

   // base case
   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; // 그 결과를 'acc'와 OR 연산자로 결합한 값을 반환
    		  // 즉, unpackGiftbox(curr, wish)이 false 면 acc 값이 리턴이 된다.
    } else {
       return acc; // 찾고자 하는 값이 나오지 않은 경우에는 현상유지 - false가 반환된다.
     }
   }, false);
   
   return result;
 }

 

• 세 가지 함수 모두 같은 결과를 반환하지만, 각각 다른 방식으로 재귀를 사용하여 구현되었다.
• 첫 번째 함수는 기본적인 반복문을 사용하여 각 요소를 확인하면서 재귀적으로 탐색한다. 이 방법은 가장 직관적인 방법이지만, 중첩된 배열이 매우 큰 경우 성능 문제가 발생할 수 있다.
• 두 번째 함수는 반복문 대신 배열을 새로운 배열에 병합하고 재귀적으로 그 배열을 다시 검색하는 방법을 사용한다. 이 방법은 첫 번째 방법보다 덜 직관적이지만, 중첩된 배열이 매우 큰 경우에도 성능이 좋을 수 있다.
• 세 번째 함수는 reduce() 메서드를 사용하여 요소를 확인하면서 재귀적으로 탐색한다. 이 방법은 두 번째 함수와 매우 유사하지만, 코드가 약간 더 간결하고 함수를 호출하는 횟수가 줄어들 수 있다.
• 중첩된 배열의 크기에 따라 성능에 영향을 받기 때문에 일반적으로는 두 번째 방법을 사용하는 것이 가장 효율적일 수 있다. 이 방법은 배열을 병합하여 불필요한 재귀 호출을 줄이는데 효과적이기 때문이다.

 

 

---

 

2. flattenArr

 

 

function flattenArr(arr) {
  // base case
  if (arr.length === 0) {
    return [];
  }
  // recursive case
  const head = arr[0];
  const tail = arr.slice(1);
  if (Array.isArray(head)) {
    return flattenArr([...head, ...tail]);
  } else {
    return [head].concat(flattenArr(tail));
  }
}

// 📌 다른 풀이 방법 1 (추천)
function flattenArr(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    if (Array.isArray(arr[i])) {
      const flattened = flattenArr(arr[i]);
      result.push(...flattened);
    } else {
      result.push(arr[i]);
    }
  }
  return result;
}


// 다른 풀이 방법 2
 function flattenArr(arr) {
   return arr.reduce(function (result, item) {
     if (Array.isArray(item)) {
       const flattened = flattenArr(item);
       return [...result, ...flattened];
     } else {
       return [...result, item];
     }
   }, []);
 }

 

• 세 가지 함수 중에서는 다른 풀이 방법 1이 가장 효율적이라고 할 수 있다.
• 이유는 첫 번째 방법은 재귀 함수를 호출할 때마다 배열을 복사하고, 전개 연산자를 사용해 다시 합쳐줘야 하는 비효율적인 과정이 있기 때문이다. 반면에 두 번째 방법은 for 루프를 사용하여 배열을 한 번 순회하며 필요한 원소들을 모두 추출하고, 그 원소들을 별도의 배열에 저장해 반환하고, 세 번째 방법은 reduce 함수를 사용하여 하나의 배열로 모든 원소를 병합한다.
• 따라서, 첫 번째 방법은 다른 방법들보다 더 많은 메모리와 계산 비용을 요구하므로 가장 비효율적이며, 두 번째 방법과 세 번째 방법 중에서는 두 번째 방법이 더 직관적이고 가독성이 좋아서, 약간 더 나은 성능을 보일 수 있다.

 

 

---

 

중

 

1. isOdd

 

 

// 🟣 for 반복문일 때
function isOdd(num) {
  if (num === 0) {
    return false;
  } else if (num === 1) {
    return true;
  }
  if (num < 0) {
    num = -num;
  }

  for (let i = 0; num >= 2; i++) {
     num = num -2;
    if (num === 1) {
    return true;
  }
  }
  return false;
}

// 🟣 while 반복문일 때
function isOdd(num) {
  if (num === 0) {
    return false;
  } else if (num === 1) {
    return true;
  }

  if (num < 0) {
    num = -num;
  }

  while (num >= 2) {
    num -= 2;
    if (num === 1) {
      return true;
    }
  }

  return false;
}

 

---

 

2. arrSum

 

문제 + 풀이 

 

---

 

3. take

 

// 내가 한 방법
function take(num, arr) {
  if(arr.length === 0 || arr.length <= num) return arr;

  return take(num, arr.slice(0, arr.length-1) )
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

// 다른 방법
function take(num, arr) {

  if (num === 0 || arr.length === 0) {
    return [];
  }

  const head = arr[0];
  const tail = arr.slice(1);

  return [head].concat(take(num - 1, tail));
}

// 디버깅

function take(num, arr) {

  if (num === 0 || arr.length === 0) {
    return [];
  }

  const head = arr[0];
  const tail = arr.slice(1);

  console.log("num:", num, "arr:", arr, "head:", head, "tail:", tail);

  return [head].concat(take(num - 1, tail));
}

take(4, [2, 4, 6, 8, 10, 12]);

// 콘솔 결과

num: 4 arr: [2, 4, 6, 8, 10, 12] head: 2 tail: [4, 6, 8, 10, 12]
num: 3 arr: [4, 6, 8, 10, 12] head: 4 tail: [6, 8, 10, 12]
num: 2 arr: [6, 8, 10, 12] head: 6 tail: [8, 10, 12]
num: 1 arr: [8, 10, 12] head: 8 tail: [10, 12]

 

• 디버깅도 좋지만 그림으로 보는 게 이해가 확실히 된다.

base case가 num === 0 일때

 

base case가 arr.length === 0 일 때

 

---

 

4. and

 

 

---

 

5. reverseArr

 

 

---

 

6. findMatryoshka

 

 

• 첫 번째 함수는 재귀 함수를 사용하여 매트료시카 객체에서 해당 크기의 객체를 찾을 때까지 객체 내부를 순환한다. 그러나 이 함수는 객체가 null이거나 속성이 없는 빈 객체인 경우에도 순환한다.
• 반면, 두 번째 함수는 재귀적으로 매트료시카 객체 내부를 검색하지만, 객체가 null이거나 찾으려는 크기보다 작은 경우 검색을 중지하고 false를 반환한다. 이 방식은 첫 번째 함수보다 더 효율적이며, 객체 내부를 불필요하게 탐색하지 않는다.
• 따라서, 두 번째 함수가 더 효율적이다.