[06.09] 재귀함수 코플릿

📌 기초적인 문제와 풀기 힘들거나 어려웠던 문제 위주

sumTo

문제 : 수(num)를 입력받아 1부터 num까지의 합을 리턴

주의사항

• number 타입을 리턴
• 1+2...num
• 재귀함수 사용/ 반복문 사용 금지
• 음수 입력은 들어오지 않아야함
• n*(n+1)/2와 같은 공식의 사용은 금지

입출력예시

let output = sumTo(10);

function sumTo(num) {
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  // basecase
  if(num <= 1) {
    return num;
  } else {
    return num+sumTo(num-1);
  }
}

---

isOdd

문제 : 수를 입력받아 홀수인지 여부를 리턴

주의사항

• 입력 : number 타입 정수
  출력 : boolean 타입 리턴
• 재귀함수 사용/ 반복문 사용금지
• 나눗셈, 나머지 연산자 사용 금지
• 0은 짝수로 간주

입출력예시

  let output = isOdd(17);
  console.log(output); // -> true

function isOdd(num) {
  // 0일경우 짝수니깐 false
  if (num === 0) {
    return false;
    // 1일경우 true 
  } else if (num === 1) {
    return true;
    // 음수일경우 양수로 만들어줌
  } else if (num < 1) {
    return isOdd(-num);
  } else {
    return isOdd(num-2);
  }
}

---

fibonacci

문제 : 수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야 합니다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

주의사항

• 입력 : number 타입 (num은 0이상 15이하의 정수)
  출력 : number 타입 리턴
• 재귀함수사용/반복문사용금지
• 피보나치 수열은 0번부터 시작

입출력예시

  let output = fibonacci(5);
  console.log(output); // -> 5

function fibonacci(num) {
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  if (num <= 1) {
    return num;
  } else if (num >= 1 && num <= 15){
    // 피보나치 n = (n-1) + (n-2)
    return fibonacci(num-1) + fibonacci(num-2);
  }
}

피보나치 풀이 그림

• (n-1) 연산이 먼저 쪼개지면서 계산이 되어진다
• (n-1) 연산이 끝나면 (n-2)연산 계산이 되어지고 합이 구해짐
  
  

---

arrSum

문제 : 배열을 입력받아 모든 요소의 합을 리턴

주의사항

• 재귀함수 사용/ 반복문 사용금지
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 입력으로 들어오는 arr의 모든 요소는 정수 값을 갖는다고 가정합니다.
• 빈 배열의 합은 0 입니다.

입출력예시

let output = arrSum([-1, -2, 1, 3]);
console.log(output); // --> 1

function arrSum(arr) {
  if (arr.length === 0) {
    return 0;
  } else {
    // 배열의 첫번째를 계속 쪼개면서 더하기
    return arr.shift() + arrSum(arr);
  }
}

---

drop

문제 : 수(num)와 배열을 입력받아 차례대호 num개의 요소가 제거된 배열을 리턴

주의사항

• 입력 : number타입(num), 배열(arr)
  출력 : 순차적으로 num개의 요소가 제거된 배열을 리턴
• 함수 drop은 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• num과 arr.length 중 최소값만큼 제거합니다.

let output = drop(2, [1, -2, 1, 3]);
console.log(output); // --> [1, 3]

function drop(num, arr) {
  if (arr.length === 0) {
    return [];
    // num이 0이 된경우 arr 반환
  } else if (num === 0) {
    return arr;
  } else {
    //num이 0이 되거나 배열에 아무것도 없을때까지 반복.
    //배열의 앞요소를 제거한 새로운 배열 
    let newArr = arr.slice(1);
    return drop(num - 1, newArr);
  }
}

---

findMatryoshka

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

주의사항

• 입력1 :
  'matryoshka', 'size' 속성을 갖는 재귀적으로 정의된 객체 (입출력 예시 참고)
  matryoshka.matryoshka는 null 또는 matryoshka 객체
  matryoshka.size는 중첩될수록 작아집니다.
  입력2 : number 타입
  출력 : boolean 타입
• 함수 findMatryoshka는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 입력받은 객체는 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 빈 객체를 입력받은 경우, false를 리턴해야 합니다.

입출력예시

const matryoshka = {
  size: 10,
  matryoshka: {
    size: 9,
    matryoshka: null,
  },
};

let output = findMatryoshka(matryoshka, 10);
console.log(output); // --> true

function findMatryoshka(matryoshka, size) {
  // 빈 객체를 확인하는 문
  if( matryoshka === null) {
    return false;
  // Object.keys(객체)넣어주면 배열로 사용가능
  } else if (Object.keys(matryoshka).length === 0){
    return false;
  // matryoshka 객체에 size와 같은 값이 있다면
  } else if(matryoshka.size === size) {
    return true;
  // matryoshka 객체 안에 또다른 객체를 찾기 위한 코드
  } else {
    return findMatryoshka(matryoshka.matryoshka, size);
  }
}  

새로 알게 된 내용

• Object.keys(객체)사용시 문자열 키 속성 이름의 배열 반환
• object1[i]는 키의 프로퍼티 값을 알수있음

const object1 = {
  a: 'somestring',
  b: 42,
  c: false
};

  console.log(Object.keys(object1));
// Expected output: Array ["a", "b", "c"]

---

unpackGiftbox

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

주의사항

• 입력1 :
  문자열, 배열을 요소로 갖는 재귀적으로 정의된 배열 (입출력 예시 참고)
  문자열은 선물 상자에 들어있는 각 선물의 이름을 의미합니다.
  배열은 더 작은 선물 상자를 의미합니다.
  입력2 : string
  출력 : boolean
• 함수 unpackGiftbox는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용이 가능합니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 빈 배열 또는 빈 문자열을 입력받은 경우, 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  

function unpackGiftbox(giftBox, wish) {
  if (wish === '' || giftBox.length === 0 ) {
    return false;
  } 
  for(let i = 0; i <= giftBox.length; i++){
    //giftbox 배열안에 wish와 같은게 있을경우
    if(giftBox[i] === wish) {
      return true
      // giftbox 배열의 배열안에 wish와 같은게 있을경우
      // -> 배열인지 아닌지르 판단하기위해 Array.isArray 메서드 사용
    } else if (Array.isArray(giftBox[i])) {
      const result = unpackGiftbox(giftBox[i], wish)
      if (result){
        return true;
      }
    }
  }
  // giftbox에 어떠한 값도 wish와 같지 않은 경우
  return false;
}

---

flattenArr

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

주의사항

• 입력 : 양의 정수 또는 배열을 요소로 갖는 다차원 배열 (입출력 예시 참고)
  출력 : 배열을 리턴해야 합니다.
• 함수 flattenArr는 재귀함수의 형태로 작성합니다.
• Array Method flat()과 flatMap() 사용은 금지됩니다.
• 반복문(for, while) 사용이 가능합니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 입력으로 전달되는 다차원 배열이 중첩된 정도(중첩의 깊이)는 정해져 있지 않습니다.
• 빈 배열을 입력받은 경우, 빈 배열을 리턴해야 합니다.

입출력예시

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

function flattenArr(arr) {
  // 빈배열일때 빈배열 리턴
  const result = []
  if(arr.length === 0 ) {
    return result;
  } 
  //반복문을 돌리면서 arr에 또다른 배열있는 확인
  for(let i = 0; i < arr.length; i++) {
    // arr에 배열이 있다면
    if(Array.isArray(arr[i])) {
      const newArr = flattenArr(arr[i]);
      result.push(...newArr);
      // arr에 배열이 없다면 그대로 리턴하게 만들어주기
    } else {
      result.push(arr[i]) ;
    }
  }
  // 반복문이 끝난뒤 각 조건에 따른 새로운 배열 리턴
  return result;
}