코플릿[자료구조/알고리즘] 재귀적 사고 연습하기 [BEB 6th]011일차

재귀재귀

[코플릿]재귀-01_sumTo

수(num)를 입력받아 1부터 num까지의 합을 리턴해야 합니다.

👻1부터 더해야한다고 1+...+num 할 고정관념에서 벗어나야한다
num=4;경우, 4+3+2+1 이렇게해도 되니깐

//코플릿:재귀 - 01.sumTo

function sumTo(num) {
  if(num <= 1) return num;
  return num + sumTo(num-1)
}
//-----------방법2. 예외처리에 차이가 있다.
function sumTo(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  if (num === 0) {
    return 0;
  } 
  if (num >= 2){
    return (num + sumTo(num-1))
  } else {
      return 1
  }
}
//-----------방법3
function sumTo(num) {
  if (num === 0) {
    return num;
  }
  return num + sumTo(num - 1);
}

잊지마팩토리얼

 

[코플릿]재귀-02_isOdd

수를 입력받아 홀수인지 여부를 리턴해야 합니다.

👻`if-else`하면, 0인경우를 제외하고 모두 else로 빠져버리니까 
(지금 우리는 총4가지 상황이 있다: 0이냐, 1이냐, 아니면 음수일경우의 재귀재귀. 또는 양수일경우의 재귀재귀)
그래서 `if-else if` 해야함

(짝홀구분할때는 나눗셈, 나머지연산자로 꼭 풀었었는데 -2씩빼는것도 재귀재귀한 방법이라는걸 알았다.)

//코플릿:재귀 - 02.isOdd
function isOdd(num) {
  if ( num === 0 ) {
    return false;
  } else if (num === 1 ) {
    return true;
  }  
  if (num < 0) {
    return isOdd(-num -2) //-2를빼서 짝홀 구분
  }else if (num >=2) { //줄생략시 아닌경우로 넘어감
    return isOdd(num -2)
  }
}
//---------
function isOdd(num) {
  if (num === 0) {
    return false;
  } else if (num === 1) {
    return true;
  }
  if (num < 0) {
    return isOdd(-num); //-2를 안해되된다고요???
  }
  return isOdd(num - 2);
}

 

[코플릿]재귀-03_factorial

n! 은 1부터 n까지 1씩 증가한 모든 값의 곱입니다.

//코플릿:재귀 - 03.factorial

function factorial(num) {
	if ( num <= 1) { //1과 0일경우 모두 예외처리
    return 1
  }
  return num * factorial(num-1)
}
//-----------방법2. 예외처리의 차이
function factorial(num) {
  if(num === 0) {
    return 1;
  }
  if(num > 1) {
    return num * factorial(num-1)
  } else {
    return 1;
  }
}

잊지말라니까팩토리얼

 

 

[코플릿]재귀-04_fibonacci

수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야 합니다.

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

입출력예시

//입출력예시
let output = fibonacci(5);
console.log(output); // --> 5

output = fibonacci(9);
console.log(output); // --> 34

👻 엌? ㅠㅠㅠㅠㅠㅠ

//코플릿:재귀 - 04.fibonacci

function fibonacci(num) {
  if ( num === 0) {
    return 0
  } else if (num === 1){
    return 1
  }
    return fibonacci(num - 1) + fibonacci(num - 2);
}
-----------
function fibonacci(num) {
  if (num <= 1) { //1과 0일때 걍 '음수'까지 num 그대로 반환ㅋ
    return num;
  }
  return fibonacci(num - 1) + fibonacci(num - 2);
}
-----------
function fibonacci(num) {
if (num <= 1){
  return num;
}
if (num >= 2) {
  return fibonacci(num - 1) + fibonacci(num -2)
}else {
  return0
}
}

 

[코플릿]재귀-05_arrSum

배열을 입력받아 모든 요소의 합을 리턴해야 합니다.

👻앞에 1개씩(머리)자르며 더하기재귀재귀

//코플릿:재귀 - 05.arrSum

function arrSum(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if ( arr.length === 0) {
    return 0;
  }
  const head = arr[0];
  const tail = arr.slice(1);
  return head+ arrSum(tail);
}
-----------
function arrSum(arr){
  if (arr.length === 0) {
    return 0;
  }
  if (arr.length > 1) {
    return arr[0] + arrSum(arr.slice(1));
  } else {
    return arr[0]
  }
}

 

[코플릿]재귀-06_arrProduct

배열을 입력받아 모든 요소의 곱을 리턴해야 합니다.

👻앞에 1개씩(머리)자르며 곱하기재귀재귀

//코플릿:재귀 - 06.arrProduct

function arrProduct(arr) {
// TODO: 여기에 코드를 작성합니다.
  if( arr.length === 0) {
    return 1;
  }
  const head = arr[0];
  const tail = arr.slice(1);
  return head * arrProduct(tail);
}

 

[코플릿]재귀-07_arrLength

배열을 입력받아 그 길이를 리턴해야 합니다.

👻isEmpty()가 내장함수인줄알았쟈나ㅏㅏㅏㅏㅏ (이문제에서만 존재하는것임; 실사용하려면 직접만들어서 사용해야함)

대략이런모습의 isEmpty()

function isEmpty(arr) {
  for (let i=0; i<arr.length; i++) {
    if (arr[i] !== undefind){
      return false;
    }
  } 
  return true;
}

arr 비었는지 체크하고 아니면(뭐가있다면), 길이체크해야하니까 1+tail

//코플릿:재귀 - 07.arrLength

function arrLength(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if (arr.isEmpty()) {
    return 0;
  }
  return 1 + arrLength(arr.slice(1)); //길이체크+뒤arr
}
//----------tail로 만들어서 넣었다는 점ㅋ
function arrLength(arr) {
  if(arr.isEmpty()) {
    return 0;
  } 
  const tail = arr.slice(1)
  return 1 + arrLength(tail);
}

 

 

[코플릿]재귀-08_drop

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

입출력예시

 

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

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

1번 입출력예시로 콘솔찍어봄

하나씩 제거하니까 num-1이구나!!!!

예외1) num === 0

예외2) arr.length === 0 -> arr (이것이 똑같이 빈배열)

예외3) num > arr.length -> []

👻하나씩 제거하니까 num-1

//코플릿:재귀 - 08.drop
function drop(num, arr) {
  if (num > arr.length){
  return [];
}
if (num >= 1) {
  return drop(num -1, arr.slice(1));
} 
  return arr; //⭐️(num === 0 || arr.length === 0) 또는 음수인경우?
}
//-------방법2. 예외처리하는데있어서의 우선순위 차이
function drop(num, arr) {
  if (num === 0 || arr.length === 0) {
    return arr;
    //num >= arr.length 경우,  return []; 안했는데도 됨??
  }
  const tail = arr.slice(1); //한번에 자르지말고 나눠서 자르자 왜? 우린 재귀하는중이니까~
  return drop(num - 1, tail);
}
//-------방법3. 예외처리하는데있어서의 우선순위 차이
function drop(num, arr) {
if (num > arr.length){
  return [];
}
if (num >= 1) {
  return drop(num -1, arr.slice(1));
}
  return arr; //이외의경우는 모두 그냥arr드림
}

 

 

[코플릿]재귀-09_take

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

입출력예시

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

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

👻8번문제는 잘라버렸던것과 달리 이번 문제는 하나씩 담아야 한다.

하나씩 담은 [배열]에 [배열]을 더해서 새로운 [배열]을 만들어야 하므로 arr.concat사용

//코플릿:재귀 - 09.take

function take(num, arr) {
  // TODO: 여기에 코드를 작성합니다.
  if ( arr.length === 0 || num === 0  ) {
    return [];
  }
  const head = arr[0];
  const tail = arr.slice(1);

  return [head].concat(take(num-1, tail)); //concat은 배열에적용되므로 arr.concat
}

 

 

[코플릿]재귀-10_and

배열을 입력받아 모든 요소의 논리곱(and)을 리턴해야 합니다.

입출력예시

//입출력예시
let output = and([true, true, true]);
console.log(output); // --> true

output = and([true, true, false]);
console.log(output); // --> false

👻논리곱and는 모두 True면 true, 한개라도 false가 있다면 false이다.

배열길이가 0이면 true를 리턴하고

1개이상일때 하나씩잘라서 비교하는데 찐논리곱&&과 재귀재귀가 이때 등장한다.

그외의 상황은 1개라면 T던 F던 하나있는거니까 그거그대로 리턴.

//코플릿:재귀 - 10.and

function and(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if( arr.length === 0 ) {
    return true;
  } 
  if (arr.length > 1 ){
    const head = arr[0];
    const tail = arr.slice(1);
    
    return head && and(tail) //하나씩잘라서 찐논리곱&& 재귀함수and 
  }else { //1개인경우
    return arr[0] 
  }
}

 

[코플릿]재귀-11_or

배열을 입력받아 모든 요소의 논리합(or)을 리턴해야 합니다.

입출력예시

//입출력예시
let output = or([true, true, false]);
console.log(output); // --> true

output = or([false, false, false]);
console.log(output); // --> false

👻10번과 비슷하지만 주의해야한다!

배열길이가 0이면 false이고,

논리곱 || or이 나오기때문에 배열길이가 1개일때도 포함해준다. (어차피 머리1개 나올꺼니까) 

//코플릿:재귀 - 11.or

function or(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if(arr.length === 0) {
    return false;
  }
  if (arr.length >= 1) {
    const head = arr[0]
    const tail = arr.slice(1)
    return head || or(tail);
  }
}
--------
function or(arr) {
  // TODO: 여기에 코드를 작성합니다.
  if(arr.length === 0) {
    return false;
  }
  const head = arr[0]
  const tail = arr.slice(1)
    
  if ( haed === true ) {
    return true;
  }
  return or(tail)
}

 

 

[코플릿]재귀-12_reverseArr

배열을 입력받아 순서가 뒤집힌 배열을 리턴해야 합니다.

입출력예시

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

👻머리가 꼭 머리가 되어야한다는(?) 고정관념을 깨버린 문제 ㅋㅋㅋ 꼬리도 머리가 될수있드아!!!

머리를 뽑아서 맨뒤로 arr.concat(arr). 이미 모두 배열들이라 따로 []감싸주지 않아도 된다.

//코플릿:재귀 - 12.reverseArr

function reverseArr(arr) {
    if (arr.length === 0) {
      return arr
    }
    const head = arr[0]
    const tail = arr.slice(1)
    return reverseArr(tail).concat(head)
}

 

 

[코플릿]재귀-13_findMatryoshka

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

입출력예시

//입출력예시
const matryoshka = {
  size: 10,
  matryoshka: {
    size: 9,
    matryoshka: null,
  },
};

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

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

👻문제와 입출력예시 이해하는데 오래걸렸던 마트료시카ㅏㅏㅏㅏ

마트료시카의 사이즈와 입력받은 사이즈가 같으면 (있다는거니까) true;

만약에 마트료시카안에 마트료시카가 null 비었다면 (없다는거니까) false;

만약에 마트로시카안에 마트로시카가 있다면, 재귀재귀

//코플릿:재귀 - 13.findMatryoshka
function findMatryoshka(matryoshka, size) {
  // TODO: 여기에 코드를 작성합니다.
  if (matryoshka.size === size) {
    return true;
  } else if (matryoshka.matryoshka === null){
    return false;
  } else if (matryoshka.matryoshka ){
    return findMatryoshka(matryoshka.matryoshka, size)
  }
  return false;

}
--------REFERENCE
function findMatryoshka(matryoshka, size) {
  // recursive case
  if (matryoshka.size === size) {
    return true;
  } else if (matryoshka.matryoshka && matryoshka.size > size) {
    return findMatryoshka(matryoshka.matryoshka, size);
  }

  // base case
  return false;
}

 

[코플릿]재귀-14_unpackGiftbox

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

입출력예시

//입출력예시
const giftBox = ['macbook', 'mugcup', ['eyephone', 'postcard'], 'money'];

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

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

👻 두가지 변수에대해 (giftBox.length === 0 || wish = '') 일경우에는 false.

for문을 이용해 하나하나 보다가 배열을 만나면! 풀어주고 ->재귀

     하나하나 보다가 일치하면 true.

이도저도아니면 false. (너선물받지뫄라)

 

Array.isArray() 는 내장함수임!! 배열인지 아닌지 true와 false로 알려줌

배열을 풀어줄때 여러가지 방법이 있는데, 

배열 그자체를 다시 재귀를 하던지, 아니면 전개연산자를 쓴다.

...전개연산자(스프레드)는 한꺼풀만 벗겨준다... (3차원 4차원 배열 다벗겨주는게아님;) concat을 쓰지않고도 (,)이걸로 붙이기도 함.

.concat은 앞,뒤 모두 배열이 여야 한다! (여기myPair sms부분은 flattenArr덕분에 배열로 변환되어서 가능한거임 🙃)

 

//코플릿:재귀 - 14.unpackGiftbox
function unpackGiftbox(giftBox, wish) {
  // TODO: 여기에 코드를 작성합니다.
 if ( giftBox.length === 0 || wish === '' ) {
   return false;
 } 
 for (let i=0; i<giftBox.length; i++) {
   if (giftBox[i] === wish) {
     return true
   } else if(Array.isArray(giftBox[i])) {//배열만나자마자
      if (unpackGiftbox(giftBox[i], wish) === true){ //⭐️걍바로재귀재귀해버림. true면 true다.
        return true;
      }
    }
} return false;
}
//------myPair sms
function unpackGiftbox(giftBox, wish) {
	if (giftBox.length === 0) return false
	for (let i=0; i<giftBox.length; i++ ) {
    	if (Array.isArray(giftBox[i])) { //⭐️배열을만났다!!
        	return unpackGiftBox([...giftBox[i], ...giftBox.slice(i+1)], wish)
            //⭐️해당배열을 한꺼풀 벗겨주고, 그 뒷부분을 잘라서 (,)이걸로 붙여준다
        }
        if (giftBox[i] === wish) return true
    }
    return false
}

-------REFERNCE 비슷
function unpackGiftbox(giftBox, wish) {
  // recursive case
  for (let i = 0; i < giftBox.length; i++) {
    if (giftBox[i] === wish) {
      return true;
    } else if (Array.isArray(giftBox[i])) {
      const result = unpackGiftbox(giftBox[i], wish);
      if (result === true) {
        return true;
      }
    }
  }

  // base case
  return false;
}

// ----------다른 풀이 방법 1 : 새로운박스를 따로 재귀
// function unpackGiftbox(giftBox, wish) {
//   // recursive case
//   let anotherBoxes = [];//⭐️새로운박스를생성했다.
//   for (let i = 0; i < giftBox.length; i++) {
//     if (giftBox[i] === wish) {
//       return true;
//     } else if (Array.isArray(giftBox[i])) { //배열을만나면 
//       anotherBoxes = anotherBoxes.concat(giftBox[i]); //새로운박스에 콘캣해준다.
//     }
//   }

//   if (anotherBoxes.length > 0) { //⭐️이박스에 있으면 따로 재귀해드림.
//     return unpackGiftbox(anotherBoxes, wish);
//   }

//   // base case
//   return false;
// }

// -----------다른 풀이 방법 2 : reduce사용
// function unpackGiftbox(giftBox, wish) {
//   const result = giftBox.reduce((acc, curr) => {
//     if (curr === wish) {
//       return true;
//     } else if (Array.isArray(curr)) { //배열을만났다!!
//       return unpackGiftbox(curr, wish) || acc; //⭐️배열을 재귀에 다시 넣넣. 근데 뒤에 '||acc'는 잘모르겟음.
//     } else {
//       return acc;
//     }
//   }, false);
//   return result;
// }

 

[코플릿]재귀-15_flattenArr

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

입출력예시

//입출력예시
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]

 

새로운빈배열을 만들어두고, 진짜 배열을 만나면 재귀써서 풀어주고 빈배열에 푸시.

    배열이 아니라면 그냥 푸시

 

//코플릿:재귀 - 15.flattenArr
// --------------------다른 풀이 방법 :reduce()사용⭐️
function flattenArr(arr) {
  return arr.reduce((result, item) => {
    if(Array.isArray(item)) {  //배열을 만났다면,
      const flattened = flattenArr(item); //재귀해주고
      return [...result, ...flattened]; //리듀스한 값+재귀한 값(풀어서넣어야 하나의 배열이되니까)
    }else {                       //배열이 아니라면,
      return [...result, item]; //리듀스한 결과 + item값
    }
  },[]); //⭐️빈배열 리턴!!
}
// --------------------다른 풀이 방법
function flattenArr(arr) {
  // TODO: 여기에 코드를 작성합니다.
  const ms = [];
  for (let i=0; i<arr.length; i++){
    if (Array.isArray(arr[i])) { //배열을만났다!
      ms.push(...flattenArr(arr[i])) //⭐️빈배열에 재귀한걸 푸시.
    } else {
      ms.push(arr[i]); //배열이아니면 그냥 푸시.
    }
  }
  return ms;
}
// --------------------다른 풀이 방법 1
// function flattenArr(arr) {
//   const result = [];
//   for (let i = 0; i < arr.length; i++) {
//     if (Array.isArray(arr[i])) {
//       const flattend = flattenArr(arr[i]); //⭐️만난 배열을 재귀
//       result.push(...flattend); //풀어서 푸시
//     } else {
//       result.push(arr[i]);
//     }
//   }
//   return result;
// }
// --------------------myPair sms
function flattenArr(arr) {
	if (arr.length === 0) return [];
    
    if (Array.isArray(arr[0]){
    	return flattenArr([...arr[0], ...arr.slice(1)]) 
        //⭐️재귀에넣을때 arr로! 스프레드로풀어넣고 (,)로붙여주고
    } else {
    	return [arr[0]].concat(flattenArr(arr.slic(1)))//⭐️머리에 연결 평평한 꼬리로 ㅋㅋ
    }
}
// --------------------REFERNCE
function flattenArr(arr) {
  // base case
  if (arr.length === 0) {
    return [];
  }

  // recursive case
  const head = arr[0];
  const tail = arr.slice(1);
  if (Array.isArray(head)) { //배열을 만났다면
    return flattenArr([...head, ...tail]); 
    //⭐️재귀에넣을때 arr로! (...)스프레드로풀어넣고 (,)로붙여주고
  } else { //배열이 아니라면
    return [head].concat(flattenArr(tail)); //⭐️머리에 연결 평평한 꼬리로 ㅋㅋ
  }
}