[개발기초] 재귀함수 - 3주차 (2)

Hong·2022년 9월 29일

👨‍💻 재귀함수라는 말 자체를 처음 들어봤다. 재귀 recursion은 작은 문재를 해결함으로써 전체 문제를 해결하는 방법을 말한다. 재귀를 사용한 코드는 대부분 더욱 간결하고 이해하기 쉬워진다.(근데 재귀의 개념을 이해해야 쉬워짐)

재쉬함수란 함수 안에서 스스로 호출된 함수를 말한다.

function foo() {
  foo();
}

이렇게 되면 계속해서 함수가 돌고 돈다.

그래서 재귀는 무한 반복을 방지하기 위해 탈출 조건이 있어야 한다.

아래와 같다.

function factorial(n) {
  if(n===0) {
    return 1;
}

💬
이렇게 개념적으로 어느정도 이해하고 코딩 문제들을 풀었다.
'어느정도' 여도 상관 없다.
수학문제나 코딩문제들은 실제로 풀어보며 1차로 두루뭉실한 개념들을 더욱 확립시키고
다시 개념으로 돌아와서 내가 이해한 개념을 더욱 단단단하게 만들어서 내공을 쌓이게 만든다.
그래서 일단 되던 안되던 풀어본다.

Matryoshka문제

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

function findMatryoshka(matryoshka, size) {
  if(!matryoshka) return false; //matryoshka가 빈 객체면 false를 return해라
  if(matryoshka.size === size) {
    return true; //만약에 matryoshka의 사이즈가 우리가 원하는 입력값의 size면 true를 return 한다.
  } else if (matryoshka.matryoshka === null || matryoshka.size < size) {
    //만약 matryoshka안의 matryoshka가 null값이거나(or),
    //matryoshka의 사이즈가 우리가 원하는 입력값의 size보다 작으면 false를 return한다.
    //이것은 더 작은 matryoshka로 들어가도 값이 우리가 원하는 size보다 작아지기 때문에 찾을 의미가 없어지기 때문에 취한 조치다.
    return false;
  } else {
    return findMatryoshka(matryoshka.matryoshka, size);
    //만약에 matryoshka안의 matryoshka가 null값이 아니거나
    //matryoshka의 사이즈가 우리가 원하는 입력값의 size보다 크면 더 작은 matryoshka로 들어가서 찾을 가치가 있기 때문에
    //findMatryoshka함수를 통해 matryoshka.matryoshka로 들어가서 우리가 원하는 size를 찾는다.
    //이 작업으로 실행되는 함수는 위의 if조건들을 다시 통과하게되며 탈출 조건에 만족할때까지 반복된다.
  }
}

입출력 예시

const matryoshka = {
  size: 10,
  matryoshka: {
    size: 9,
    matryoshka: null,
  },
};
//이렇게 matryoshka안에 또 matryoshka가 있다. 
//matryoshka는 객체고 객체 안의 또 다른 객체는 점점 size가 작아진다.

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

output = findMatryoshka(matryoshka, 8);
console.log(output); // --> false

💬
솔직히 처음에 정답을 알기 전까지 뭔말인지 한참을 고민했는데 이해하고 나니 별거 아니다.

unpackGiftbox문제

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

function unpackGiftbox(giftBox, wish) {
  for(let i = 0 ; giftBox.length > i ; i++) {
    //for문을 통해 i=0부터 시작해서 gift.length보다 작을때 까지 아래를 반복한다. i는 하나씩 커짐
    if(giftBox[i] === wish) return true;
    //i를 0부터 끝까지 계속 돌리다가 우리가 원하는 wish값이 나오면 true를 return한다.
    if(Array.isArray(giftBox[i])) {
      if(unpackGiftbox(giftBox[i], wish)) return true;
    }
    //근데 문제는 giftbox배열 안에 또 다시 배열이 존재할 수 있다는 것이다.
    //Array.isArray() 배열 method를 통해 i순서의 giftbox배열이 array인지 판별한다.
    //만약 그것이 참이라면(giftbox[i]가 배열이라면) 이것을 unpackGiftbox함수에 인자로 넣고 돌린다.
    //만약 배열안의 배열인 giftbox[i]안에 우리가 원하는 wish값이 있다면 true를 return한다.
    //재귀적으로 생각할 부분은 여기서 들어갈 giftbox[i]의 요소들은 for문에서 적었던 필터링을 다시 거쳐 내려온다는 것이다. 
  }
  return false;
  //만약 for문과 재귀함수를 끝까지 돌렸음에도 우리가 찾는 wish값이 없다면 false를 return한다.
}

입출력 예시

const giftBox = ['macbook', 'mugcup', ['eyephone', 'postcard'], 'money'];
//giftbox배열 안에 도 배열이 존재할 수 있고, 배열안의 요소들은 문자열로 존재한다.

let output = unpackGiftbox(giftBox, 'iphone');
console.log(output); // --> false

output = unpackGiftbox(giftBox, 'postcard');
console.log(output); // --> true

💬
어렵지만 이것도 이해 완료

flattenArr문제

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

function flattenArr(arr) {
  let result = [];
  for(let i = 0 ; arr.length > i ; i++) {
    //for문을 통해 arr배열의 모든 요소들을 순회한다.
    if(typeof arr[i] === 'number') {
      result.push(arr[i]);
      //근데 순회하는 과정에서 arr[i]가 숫자면, 빈배열 result에 넣는다.(arr은 양의 정수만 배열의 요소로 가짐)
    } else {
      let flat = flattenArr(arr[i]);
      result.push(...flat);
      //만약 숫자가 아니라면 flatternArr(arr[i])를 통해 []을 벗긴다음 다시 위로 돌아가 함수를 위에서 아래로 실행시킨다.
      //만약 []를 벗기고 벗겨서 flat배열 안에(result = []로 인해 만들어짐) 숫자가 있다면.
      //제일 처음 함수를 실행시킬 때 만들어진 result=[]배열에 push한다.
    }
  }
  return result;
  //위의 과정이 끝나면 result를 return한다.
}

입출력 예시

let output = flattenArr([[1], 2, [3, 4], 5]);
console.log(output); // --> [1, 2, 3, 4, 5]
//이렇게 아무리 배열안에 배열이 많아도 1차원 배열로 만들어주는 함수다.

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