TIL : 재귀함수

1. 재귀(recursion)

어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법

---

2. 재귀함수

어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수

---

3.  재귀함수를 사용하는 경우

- 주어진 문제가 구조는 비슷하고 더 작은 문제로 나뉘어질 수 있는 경우

- 중첩된 루프가 많거나 중첩의 정도를 미리 알 수 없는 경우

---

4. 재귀적으로 사고하기

(1) 재귀 함수의 입력값과 출력값 정의하기

(2) 문제를 쪼개고 경우의 수를 나누기

(3) 단순한 문제 해결하기

(4) 복잡한 문제 해결하기

(5) 코드 구현하기

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

---

5. 재귀함수 예제

1. 수를 입력받아 n-factorial(n!) 값을 리턴해야 합니다.
function factorial (num) {
  if (num === 0) {
    return 1;
  } return num * factorial (num - 1);
}

2. 배열을 입력받아 순서가 뒤집힌 배열을 리턴해야 합니다.
function reverseArr(arr) {
  let head = arr[0];
  let tail = arr.slice(1);
  if (arr.length === 0) {
    return [];
  } return reverseArr(tail).concat(head);
}

3. 선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아 조건에 맞는 선물이 있는지 여부를 리턴해야 합니다.
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]);
//     }
//   }

//   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;
//     } else {
//       return acc;
//     }
//   }, false);
//   return result;
// }

4. 다차원 배열을 입력받아 1차원 배열로 변환하여 리턴해야 합니다.
function flattenArr(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    if(Array.isArray(arr[i]) === true) {
      newArr = newArr.concat(flattenArr(arr[i]))
    } else {
      newArr.push(arr[i])
    }
  } return newArr;
}

개인적으로 3번 문제가 가장 어려웠다. 첫 번째 방법으로 풀었는데 result로 선언해서 true인지 확인하는 과정을 거치지 않았는데 계속해서 통과가 되지 않았고 계속 고민하다 겨우겨우 풀었다ㅠㅠ