재귀(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) === 002_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) === 104_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) === 005_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([]) === 006_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
// 빈 배열의 논리곱은 true11_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
// 빈 배열의 논리합은 false12_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!