재귀

재귀함수를 이용한 문제풀이

---

base case / recursive case

• base case : 재귀의 기초로 재귀적으로 문제를 해결할 필요 업시 바로 답을 알 수 있는 경우(=재귀의 탈출 조건)을 의미합니다.
• recursive case : 재귀적으로 부분문제를 푸는 경우를 의미합니다.

---

09_take

문제

수(num)와 배열을 입력받아 차례대로 num개의 요소만 포함된 새로운 배열을 리턴해야 합니다.

 

입력

인자 1 : num

• number 타입의 정수 (num >= 0)

인자 2 : arr

• 임의의 요소를 갖는 배열

출력

• 순차적으로 num 개의 요소로 구성된 배열을 리턴해야 합니다.

function take(num, arr) {
  // base case : num(빼야할 수)가 0이거나 arr에 더는 뺄 요소가 없을 경우
  if(num===0 || arr[1] === undefined) {
    // num이 처음부터 0이 들어오면 빈 배열 리턴
    return Array.isArray(arr[0]) ? arr[0] : []
  }

  // recursive case : 첫 번째 재귀와 그 이후 재귀
  // 처음에는 arr[0] 이 배열이 아니므로 [arr[0],...] 형태로 만들어준다.
  if(Array.isArray(arr[0])){
    return take(num-1,[[...arr[0],arr[1]],...arr.slice(2)])
  } else {
    return take(num-1,[[arr[0]],...arr.slice(1)])
  }
}

 

 

---

 

13_findMatroyoshka

문제

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

 

입력

인자 1 : matryoshka

• 'matryoshka', 'size' 속성을 갖는 재귀적으로 정의된 객체 (입출력 예시 참고)
• matryoshka.matryoshka는 null 또는 matryoshka 객체
• matryoshka.size는 중첩될수록 작아집니다.

인자 2 : size

• number 타입의 수

출력

• boolean 타입을 리턴해야 합니다.

function findMatryoshka(matryoshka, size) {

  // 객체 내부에 있는 객체도 탐색해야 합니다.
  
  // base case1 : 조사할 객체가 없는 경우
  if(Object.keys(matryoshka).length===0) return false;
  // base case2 : 해당 조건에 맞는 인형이 있을 경우
  if(matryoshka.size === size) return true;
  // base case3 : 더 조사할 객체가 없는 경우
  if(matryoshka.matryoshka === null) return false;

  // 객체 내부 객체도 조사하기 위해 재귀
  return findMatryoshka(matryoshka.matryoshka,size)
}

 

---

 

15_flattenArr

문제

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

 

입력

인자 1 : arr

• 양의 정수 또는 배열을 요소로 갖는 다차원 배열

출력

• 배열을 리턴해야 합니다.

function flattenArr(arr) {

  let returnArr = []
  // for of를 사용해 요소 하나씩 접근한다.
  for(ele of arr) {
    // 해당 요소가 배열일 경우 해당 요소를 재귀시켜 반환된 값을 반환값에 추가한다.
    if(Array.isArray(ele)){
      // spread를 사용한 방법
      // returnArr.push(...flattenArr(ele))
      // concat을 사용한 방법
      returnArr = returnArr.concat(flattenArr(ele))
    } else {
      // 해당 요소가 배열이 아닌 값일 때는 다른 작업없이 바로 반환값에 추가한다.
      returnArr.push(ele)
    }
  }
  return returnArr
}