[코플릿] 재귀

비트·2023년 6월 9일

재귀함수 코드스테이츠 코플릿

CodeStates

목록 보기

42/54

재귀(`recursion`) 함수

재귀(recursion) 함수 정리 보러가기

`01_sumTo`

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

풀이.

function sumTo(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  
  // base case
  // if (num === 0 ) return 0
  if (num <= 1 ) return num

  // recursive case
  return sumTo(num - 1) + num
}


// 풀이

// recursive case : 문제를 동일한 방식으로 쪼개나가는 방법
// sumTo(5) === 1 + 2 + 3 + 4 + 5
// sumTo(5) === sumTo(4) + 5

// sumTo(4) === 1 + 2 + 3 + 4
// sumTo(4) === sumTo(3) + 4

// sumTo(3) === 1 + 2 + 3 
// sumTo(3) === sumTo(2) + 3

// sumTo(2) === 1 + 2 
// sumTo(2) === sumTo(1) + 2

// 따라서, 
// => sumTo(num) ===sumTo(num - 1) + num

// base case : 문제가 더이상 쪼개지지 않는 순간 -> 탈출 조건 작성!
// sumTo(1) === 1 
// sumTo(0) === 0

`02_isOdd`

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

풀이.

function isOdd(num) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (num === 1) {
    return true;
  } else if(num === 0) {
    return false;
  }

  // recursive case
  if (num < 0) {
    return isOdd(num + 2);
  } else if (num > 0) {
    return isOdd (num - 2);
  }
}


// 풀이

// recursive case
// num === 9
// 9 - 2 - 2 - 2 - 2 = 1
// num === -9
// -9 + 2 + 2 + 2 + 2 = 1

// base case
// sumTo(1) === 1 (true)
// sumTo(0) === 0 (false)

`03_factorial`

문제.
수를 입력받아 n-factorial(n!; 엔-팩토리얼) 값을 리턴해야 합니다.
n! 은 1부터 n까지 1씩 증가한 모든 값의 곱입니다.

풀이.

function factorial(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.

  // base case
  if (num <= 1) {
    return 1
  }

  // recursive case
  return factorial(num - 1) * num
}


// 풀이

// recursive case
// factorial(5) === 1 * 2 * 3 * 4 * 5
// factorial(5) === factorial(4) * 5
// => factorial(num) === factorial(num - 1) * num

// base case
// factorial(1) === 1
// factorial(0) === 1

`04_fibonacci`

문제.
수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야 합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

풀이.

function fibonacci(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.

  // base case
  if (num === 0) {
    return 0;
  } else if (num === 1) {
    return 1;
  }

  // recursive case
  return fibonacci(num - 1)  +fibonacci(num - 2);
}


// 풀이

// recursive case
// fibonacci(num) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
// 현재 번째 수는 (전 번째)와 (전전 번째)의 합
// num === num-1 + num-2

// base case
// fibonacci(1) === 1
// fibonacci(0) === 0

`05_arrSum`

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

풀이.

function arrSum(arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (arr.length === 0) {
    return 0;
  }

  // recursive case
return arr[0] + arrSum(arr.slice(1))
}


// 풀이

// const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];
// console.log(animals.slice(1));
// output : ['bison', 'camel', 'duck', 'elephant']


// recursive case
// arr[0] + arr[1] + ... + arr[n-1]
// arr.length === n
// arr[1번째 인덱스] ~ arr[마지막 인덱스까지]
// => arr[0] + arrSum(arr.slice(1))

// base case
// 빈 배열의 합은 0 입니다.
// arrSum([]) === 0

`06_arrProduct`

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

풀이.

function arrProduct(arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (arr.length === 0) {
    return 1;
  }

  // recursive case
   return arr[0] * arrProduct(arr.slice(1))
}


// 풀이

// recursive case
// arr[0] * arr[1] * ... * arr[n-1]
// arr.length === n
// arr[1번째 인덱스] ~ arr[마지막 인덱스]
// => arr[0] * arrProduct(arr.slice(1))

// base case
// 빈 배열의 곱은 1
// // arrProduct([]) === 1

`07_arrLength`

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

풀이.

function arrLength(arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (arr.isEmpty()) {
    return 0;
  }

  // recursive case
  return 1 + arrLength(arr.slice(1));
}


// 풀이

// recursive case
// 배열을 입력받아 그 길이를 리턴

// arr = [1, 2, 3] 인 경우,

//  arr.isEmpty()는 false 이므로 if문은 건너뛰고
//  return에 걸린 1 + arrLength([2,3]) 실행

//  arrLength([2,3]) -> return 1 + arrLength([3])
//  arrLength([3]) -> return 1 + arrLength([])
//  arrLength([]) -> arr.isEmpty()가 true 이므로 return 0

//  1 + arrLength([2,3])
//  1 + 1 + arrLength([3])
//  1 + 1 + 1 + arrLength([])
//  1 + 1 + 1 + 0

//  리턴 값은 3!


// base case
// arr.isEmpty()를 통해 배열이 비어있는지 확인할 수 있습니다. (커스텀 메소드)
// 빈 배열의 길이는 0
// arrLength ([]) === 0

`08_drop`

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

풀이.

function drop(num, arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (arr.length < num) {
    return [];
  } else if (num === 0) {
    return arr;
  }
  // if (num === 0 || arr.length === 0) {
  //   return arr;
  // }

  // recursive case
  return drop(num-1,arr.slice(1));
}


// 풀이

// recursive case
// 순차적으로 num 개의 요소가 제거된 배열을 리턴
// 인덱스 1번째 자리는 0번이므로 num 값에 -1을 해줘야 함.

// base case
// arr.length보다 num이 크면 빈 배열 리턴
// num이 없을 경우 기존 배열 리턴

`09_take`

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

풀이.

function take(num, arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (num === 0 || arr.length === 0) {
    return [];
  }
  // if (num === 0) {
  //   return [];
  // } else if (arr.length < num) {
  //   return arr;
  // }
  

  // recursive case
   return [arr[0]].concat(take(num-1,arr.slice(1)));
  // return [].concat(arr[0],take(num-1,arr.slice(1)))
  
}


// 풀이

// recursive case
// 순차적으로 num 개의 요소가 제거된 배열을 리턴
// 인덱스 1번째 자리는 0번이므로 num 값에 -1을 해줘야 함.

// base case
// arr.length보다 num이 크면 빈 배열 리턴
// num이 없을 경우 기존 배열 리턴

`10_and`

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

풀이.

function and(arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (arr.length === 0) {
    return true;
  }

  // recursive case
  return arr[0] && and(arr.slice(1));
}


// 풀이

// recursive case
// 배열을 입력받아 모든 요소의 논리곱(and)을 리턴

// base case
// 빈 배열의 논리곱은 true

`11_or`

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

풀이.

function or(arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (arr.length === 0) {
    return false;
  }

  // recursive case
  return arr[0] || or(arr.slice(1));
}


// 풀이

// recursive case
// 배열을 입력받아 모든 요소의 논리합(or)을 리턴

// base case
// 빈 배열의 논리합은 false

`12_reverseArr`

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

풀이.

function reverseArr(arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (arr.length === 0) {
    return arr;
  }

  // recursive case
  return [...reverseArr(arr.slice(1)),arr[0]];
  // return reverseArr(arr.slice(1)).concat(arr[0]);
}


// 풀이

// recursive case
// 배열을 입력받아 순서가 뒤집힌 배열을 리턴

// base case
// 빈 배열은 빈 배열 그대로를 리턴

`13_findMatryoshka`

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

풀이.

function findMatryoshka(matryoshka, size) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (Object.keys(matryoshka).length === 0) {
    return false;
  }

  // recursive case
  if (matryoshka.size === size) {
    return true;
  } else if (matryoshka.matryoshka === null) {
    return false;
  } else
  return findMatryoshka(matryoshka.matryoshka,size);
}


// 풀이

// recursive case
// 정보를 담은 객체와 수를 입력받아 조건에 맞는 인형이 있는지 여부를 리턴
// 현재 인형의 size와 입력된 size를 비교
// matryoshka 객체가 null인 경우 false를 반환
// matryoshka 객체가 있는 경우 재귀적으로 호출하여 내부 인형을 검사

// base case
// 빈 객체를 입력받은 경우, false를 리턴

`14_unpackGiftbox`

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

풀이.

function unpackGiftbox(giftBox, wish) {
  // TODO: 여기에 코드를 작성합니다.

  // recursive case
  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)) {
        return true;
      }
    }
  }
  
  // base case
  return false;
}


// 풀이

// recursive case
// 1. giftBox에 배열을 순회
// 2. giftBox 배열 안에 wish가 일치한다면?
// 3. true를 반환
// 4. Array.isArray([i]]) === true 라면? 즉, 배열이라면?
// 5. 그리고, unpackGiftbox함수에 매개변수로 (giftBox[i], wish) 주고, 일치한다면?
// 6. true를 반환

// base case
// 빈 배열 또는 빈 문자열을 입력받은 경우, false를 리턴

`15_flattenArr`

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

풀이.

function flattenArr(arr) {
  // TODO: 여기에 코드를 작성합니다.

  // base case
  if (arr.length === 0) {
    return arr;
  }

  // recursive case
  if (Array.isArray(arr[0])) { 
    return flattenArr ([...arr[0],...arr.slice(1)]); 
  } else {
    return [arr[0]].concat(flattenArr(arr.slice(1)));
  }
}


// 풀이

// arr 배열의 첫번째 요소가 배열인지 확인.

// 배열이라면 스프레드 연산자를 사용하여 평탄화.
// 평탄화한 배열과 arr.slice(1)의 나머지 부분을 결합.

// 배열이 아니라면,
// 해당 요소를 그대로 갖는 배열로 생성.
// arr.slice(1)을 통해 배열의 첫 번째 요소를 제외한 나머지 부분을 새로운 배열로 만든다.

풀이 2.

function flattenArr(arr) {
  let result = [];

  for (let i = 0; i < arr.length; i++) {

    if (Array.isArray(arr[i])) {
      result = result.concat(flattenArr(arr[i]));
    } else {
      result.push(arr[i]);
    }
  }
  return result;
}


// 풀이

// result라는 변수에 빈 배열을 만들고,
// 1. arr에 배열을 순회
// 2. Array.isArray([i]) === true라면? 즉 배열이라면?
// 3. 새로운 배열을 만들어서 result 변수에 할당
// 4. 아니면, 기존의 result 배열을 직접 변경

비트

Drop the Bit!

이전 포스트

Day +41

다음 포스트

[코플릿] 재귀

CodeStates

재귀(`recursion`) 함수

`01_sumTo`

`02_isOdd`

`03_factorial`

`04_fibonacci`

`05_arrSum`

`06_arrProduct`

`07_arrLength`

`08_drop`

`09_take`

`10_and`

`11_or`

`12_reverseArr`

`13_findMatryoshka`

`14_unpackGiftbox`

`15_flattenArr`

Day +41

Day +42

0개의 댓글