[야간자율학습반 ] 재귀

오늘은 종합퀴즈에서 무려 67.5%라는 처참한 정답률을 기록한 나를 위해

코드스테이츠에서 야간 자율학습을 마련해 주셨다,..,.,,.,..,,,,

썩 오고싶진 않았지만, 이왕 온 김에 나에 부족한 점을 되돌아보는 시간을 가져보자!

 

야자반의 과제는 재귀 연습문제중 3개를 골라 푸는 것이다.

내가 풀면서 조금 헷갈렸던 문제들을 골라 한번 풀어보겠다.

---

09. take

문제 수(num)와 배열을 입력받아 차례대로 num개의 요소만 포함된 새로운 배열을 리턴해야 합니다. 입력 인자 1 : num number 타입의 정수 (num >= 0) 인자 2 : arr 임의의 요소를 갖는 배열 출력 순차적으로 num 개의 요소로 구성된 배열을 리턴해야 합니다. 주의 사항 함수 take는 재귀함수의 형태로 작성합니다. 반복문(for, while) 사용은 금지됩니다. 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).

 

의사 코드

종료 조건 : num이 0이 되는 경우 or num이 arr의 길이보다 큰 경우

• num이 0이 되는 경우는 빈 배열을 return
• num이 arr의 길이보다 큰 경우는 배열 전체를 return

재귀 : 배열의 첫번째 요소들만 num번 이어 붙여야 한다

• 한 배열의 첫 요소를 붙이면 다음 재귀에서 이어붙여야 할 요소는 num-1개이므로, num =>  num-1
• 다음 재귀에서 사용하는 배열은 첫 배열을 삭제한 배열. 이때, 원본 배열을 건들면 안되므로 복사를 실시.
• slice(1)로 첫 요소를 제외한 배열을 arr로 넘김.
• 최종적으로 하나의 배열을 return해야 하므로, 전개연산자(...)를 통해 배열을 펼쳐 새 배열 생성

코드

function take(num, arr) {
  if(num > arr.length){
    return arr
  }
  else if(num === 0){
    return []
  }
  return [arr[0], ...take(num - 1, arr.slice(1))]
}

---

11. or

문제 배열을 입력받아 모든 요소의 논리합(or)을 리턴해야 합니다. 입력 인자 1 : arr boolean 타입을 구성 요소로 갖는 배열 출력 boolean 타입을 리턴해야 합니다. arr[0] || arr[1] || ... || arr[n-1] arr.length는 n 주의 사항 함수 or는 재귀함수의 형태로 작성합니다. 반복문(for, while) 사용은 금지됩니다. 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability). 빈 배열의 논리합은 false 입니다.

 

의사 코드

종료 조건 : arr의 길이가 0이 되는 경우(더이상 비교할 요소가 없을 때)

• or은 비교 요소들 중 하나만 true여도 true이므로, 비교할 요소가 없을 땐 false를 return

재귀 : 배열의 첫번째 요소와, 그 다음 배열의 첫번째 요소를 비교해야 한다

• (((첫 요소 || 이전 배열의 첫 요소) || 이전 배열의 첫 요소) || ...) 의 형태를 지니고 있어야 함
• 따라서, 현재 배열의 첫 요소와 첫 요소를 잘라낸 배열에 or을 적용한 배열을 비교해야 함
• 재귀가 끝까지 실행되면, 종료 조건의 false와 직전 배열의 값을 비교. 

코드

function or(arr) {
  if(arr.length < 1){
    return false
  }
  return arr[0] || or(arr.slice(1))
}

---

14. unpackGitfbox

문제 선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아 조건에 맞는 선물이 있는지 여부를 리턴해야 합니다. 입력 인자 1 : giftBox 문자열, 배열을 요소로 갖는 재귀적으로 정의된 배열 (입출력 예시 참고) 문자열은 선물 상자에 들어있는 각 선물의 이름을 의미합니다. 배열은 더 작은 선물 상자를 의미합니다. 인자 2 : wish string 타입의 문자열 출력 boolean 타입을 리턴해야 합니다. 주의 사항 함수 unpackGiftbox는 재귀함수의 형태로 작성합니다. 반복문(for, while) 사용이 가능합니다. 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability). 빈 배열 또는 빈 문자열을 입력받은 경우, false를 리턴해야 합니다.

 

의사 코드

종료 조건 : giftbox의 길이가 0일 때

or

giftbox에 wish가 포함되어 있을 때

• giftbox의 길이가 0이면 주어진 wish가 없으므로 false return
• wish가 포함되어 있으면 true return

재귀 : 배열의 첫번째 요소와, 그 다음 배열의 첫번째 요소를 비교해야 한다

• 배열 안에 배열이 들어 있으므로, 우선 첫 배열의 요소들을 종료 조건의 includes를 통해 스캔
• 만약 첫 배열 안에 wish가 있으면 true return. 없을 경우 배열 내의 배열을 찾음
• 첫 배열을 순회해 배열이 있다면 해당 배열을 다음 재귀의 arr로 전달
• wish는 변함이 없음
• 다음 재귀는 배열 내의 배열에서 실행

코드

function unpackGiftbox(giftBox, wish) {
  if(giftBox.length < 1){
    return false
  } if(giftBox.includes(wish)){
    return true
  }
  let newArr = []
  for(let i = 0; i <giftBox.length; i++){
    if(Array.isArray(giftBox[i])){
      newArr = giftBox[i]
    }
  }
  return unpackGiftbox(newArr, wish)
}

---

야간자율학습반!

즐거웠고~ 다음엔 보지 말자!