[JavaScript] 재귀

2022.12.18

💡 재귀의 이해

재귀 : 원래의 자리로 되돌아가거나 되돌아옴.

자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행된다.

재귀는 Base Case와 Recursion Case로 구분해서 해결하면 문제해결이 좀 더 쉬워진다.

📌 재귀는 언제 사용하는게 좋을까?

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• **중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우 **

모든 재귀 함수는 반복문으로 표현할 수 있다. 그러나 재귀를 사용할 수 있는 대부분의 경우에는 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    } 
                }
            }
        }
    }
 }

📌 재귀로 문제해결

1. 문제를 작게 쪼개기
2. 더이상 작아지지 않을 때 까지, 가장 작은 단위로 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결

💡 재귀함수의 활용

재귀적으로 사고하여 문제 풀기

1. 재귀 함수의 입력값과 출력값 정의

재귀적 사고하는 데에 가장 먼저 해야 하는것은 단순하게 함수의 입출력값을 정의 하는것이다.

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

문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분한다.

3. 단순한 문제 해결

문제를 여러 경우로 구분한 다음에는, 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)라고 부른다. 재귀의 기초(base case)는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

탈출 조건이 없는 경우 재귀 함수는 끝없이 자기 자신을 호출하게 된다.

4. 복잡한 문제 해결

남아있는 복잡한 경우를 해결한다.

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

💡 재귀함수 코플릿 문제

문제1

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

풀이

function unpackGiftbox(giftBox, wish) {
  // TODO: 여기에 코드를 작성합니다.
  // boolean 타입을 리턴받는다.

  // recursive case
  for (let i = 0; i < giftBox.length; i++) {
    // giftBox가 wish와 같다면
    if (giftBox[i] === wish) {
      return true;
    }
    // giftBox 요소중에 배열이며 wish와 같다면
    else if (Array.isArray(giftBox[i])) {
      const result = unpackGiftbox(giftBox[i], wish);
      if (result === true) {
        return true;
      }
    }
  }
  // base case
  // 빈 배열 또는 빈 문자열을 입력받은 경우, false를 리턴받는다.
  return 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

반복문으로 배열을 나열해준뒤에 조건문을 통해 Array.isArray를 활용했다

그 결과 배열 속 배열값을 찾을 수 있었고 변수에 담아서 비교하여 해결 할 수 있었다.

문제2

: 다차원 배열을 입력받아 1차원 배열로 변환하여 리턴해야 합니다.

풀이

function flattenArr(arr) {
  // TODO: 여기에 코드를 작성합니다.
  // 반복문 사용 가능
  
  for(let i = 0; i<arr.length; i++){
    // 요소중에 배열이 있으면? -> 배열 풀어주기
    if(Array.isArray(arr[i])){
      // 요소중에 배열을 중심으로 앞 뒤로 나눠주기
      let front = arr.slice(0, i)
      let middle = arr[i]
      let back = arr.slice(i+1)
      // 나눠준 요소를 다시 합쳐준다
      let flatten = [...front, ...middle, ...back]
      return flattenArr(flatten)
    }
  }
  return arr
}



//입출력 예시
let output = flattenArr([[1], 2, [3, 4], 5]);
console.log(output); // --> [1, 2, 3, 4, 5]

output = flattenArr([[2, [[3]]], 4, [[[5]]]);
console.log(output); // --> [2, 3, 4, 5]

이전 문제와 동일하게 Array.isArray를 활용하여 배열 속 배열값을 찾고

front, middle, back 변수에 담아서 flatten에서 [...] 비구조화 할당을 통하여 문제를 해결할수있었다.