🔎 재귀 함수에 익숙해지기 위해서 풀었던 코플릿 문제들 중 몇가지를 다시 풀어보면서 복습하고, 조금 더 재귀적 사고에 익숙해져보려고 한다.
1. sumTo
문제
수(num)를 입력받아 1부터 num까지의 합을 리턴해야 합니다.
입력
인자 1 : num
number 타입의 정수 (num >= 0)출력
number 타입을 리턴해야 합니다.
1 + 2 + ... + num주의 사항
함수 sumTo는 재귀함수의 형태로 작성합니다.
반복문(for, while) 사용은 금지됩니다.
n * (n + 1) / 2 와 같은 공식의 사용은 금지됩니다.
음수 입력은 들어오지 않습니다.입출력 예시
let output = sumTo(10); console.log(output); // --> 55힌트
sumTo(n)은 자연수 1부터 n까지의 합을 계산하는 함수입니다. sumTo(1) = 1 sumTo(2) = 1 + 2 = 3 sumTo(3) = 1 + 2 + 3 = 6 sumTo(4) = 1 + 2 + 3 + 4 = 10💻 문제 해결
function sumTo(num) { //base case if(num <= 1) { return num; } //recursive case return num + sumTo(num - 1); } //sumTo(0) = 0 => 더 이상 쪼개지지 않는 경우 //sumTo(1) = 1 => 더 이상 쪼개지지 않는 경우 //sumTo(2) = sumTo(1) + 2 // ... //sumTo(4) = sumTo(3) + 4 //sumTo(5) = sumTo(4) + 5 //sumTo(num) = sumTo(num-1) + num }
2. fibonacci
> 문제
수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야 합니다.
0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...입력
인자 1 : num
number 타입의 num (num은 0 이상 15 이하의 정수)출력
number 타입을 리턴해야 합니다. (num 번째 피보나치 수)
주의 사항
함수 fibonacci는 재귀함수의 형태로 작성합니다.
반복문(for, while) 사용은 금지됩니다.
피보나치 수열은 0번부터 시작합니다.입출력 예시
let output = fibonacci(5); console.log(output); // --> 5 output = fibonacci(9); console.log(output); // --> 34💻 문제 해결
function fibonacci(num) { //base case if(num <= 1){ return num } //recursive case fibonacci(num) = fibonacci(num-2) + fibonacci(num-1) } //base case //fibonacci(0) = 0 //fibonacci(1) = 1 //fibonacci(2) = fibonacci(0) + fibonacci(1) //recursive case //fibonacci(num) = fibonacci(num-2) + fibonacci(num-1)
3. findMatryoshka
문제
러시아 전통인형 마트료시카에 대한 정보를 담은 객체와 수를 입력받아 조건에 맞는 인형이 있는지 여부를 리턴해야 합니다.
입력
인자 1 : matryoshka
'matryoshka', 'size' 속성을 갖는 재귀적으로 정의된 객체 (입출력 예시 참고)
matryoshka.matryoshka는 null 또는 matryoshka 객체
matryoshka.size는 중첩될수록 작아집니다.
인자 2 : size
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 output = findMatryoshka(matryoshka, 8); console.log(output); // --> false💻 문제 해결
function findMatryoshka(matryoshka, size) { //base case => 원하는 사이즈의 마트료시카를 찾았을 때 if(matryoshka.size === size){ return true; } //recursive case //=> 원하는 사이즈의 마트료시카가 아니면서 안에 마트료시카가 또 있을 때 if (matryoshka.matryoshka){ return findMatryoshka(matryoshka.matryoshka, size); } //나머지 return false; }
4. unpackGiftbox (⭐️⭐️⭐️)
문제
선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아 조건에 맞는 선물이 있는지 여부를 리턴해야 합니다.
입력
인자 1 : giftBox
문자열, 배열을 요소로 갖는 재귀적으로 정의된 배열 (입출력 예시 참고)
문자열은 선물 상자에 들어있는 각 선물의 이름을 의미합니다.
배열은 더 작은 선물 상자를 의미합니다.
인자 2 : wish
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) { for(let gift of giftBox){ //base case if(gift === wish){ return true } //recursive case if(Array.isArray(gift)) { if(unpackGiftbox(gift,wish) === true) { return true } } } //나머자 return false }📍 체크
for...of명령문은 반복가능한 객체 (Array, Map, Set, String, TypedArray, arguments 객체 등을 포함)에 대해서 반복하고 각 개별 속성값에 대해 실행되는 문이 있는 사용자 정의 반복 후크를 호출하는 루프를 생성합니다.const array1 = ['a', 'b', 'c']; for (const element of array1) { console.log(element); } // expected output: "a" // expected output: "b" // expected output: "c"
5. flattenArr (⭐️⭐️⭐️)
문제
다차원 배열을 입력받아 1차원 배열로 변환하여 리턴해야 합니다.
입력
인자 1 : arr
양의 정수 또는 배열을 요소로 갖는 다차원 배열 (입출력 예시 참고)출력
배열을 리턴해야 합니다.
주의 사항
함수 flattenArr는 재귀함수의 형태로 작성합니다.
Array Method flat()과 flatMap() 사용은 금지됩니다.
반복문(for, while) 사용이 가능합니다.
입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
입력으로 전달되는 다차원 배열이 중첩된 정도(중첩의 깊이)는 정해져 있지 않습니다.
빈 배열을 입력받은 경우, 빈 배열을 리턴해야 합니다.입출력 예시
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]💻 문제 해결
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]); } else { return [head].concat(flattenArr(tail)); } } //반복문으로 요소를 쭉 확인 //요소가 배열이면 -> 대괄호 까주기 //요소가 숫자면 -> 그냥 냅두기 //[1,2,[3,4],5] //[1,2][3,4][5] //[...[1,2],...[3,4],...[5]] //[1,2,3,4,5]
