재귀함수

재귀함수란?

A라는 함수의 내용 안에 A 자기 자신이 호출되어 반복적으로 실행되는 함수

< 언제 사용하는가? >

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

재귀함수를 사용하면 코드를 더 간결하고 직관적으로 이해할 수 있게 작성할 수 있다.

< 재귀적 문제 해결 시퀀스 >

1. 재귀 함수의 입력값과 출력값 정의하기
2. 문제를 쪼개고 경우의 수를 나누기
3. 단순한 문제 해결하기
4. 복잡한 문제 해결하기
5. 코드 구현하기
   
   
   

---

< 03. 문제 : 수를 입력받아 n-factorial(n!; 엔-팩토리얼) 값을 리턴해야 합니다.

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

입출력 예시

let output = factorial(10);
console.log(output); // --> 3628800

정답

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

return num * factorial(num-1)
}

---

< 04. 문제 : 수(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

정답

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

---

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

입출력 예시

 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) {
  // TODO: 여기에 코드를 작성합니다.
if(matryoshka.size === size){ // 표면의 마트로시카의 사이즈와 같다면 트루 리턴
  return true
}
else if(matryoshka.matryoshka && matryoshka.size > size){ // 아니고 마트로시카 안에 마트로시카라는 키값이 있고 마트로시카의 사이즈가 제시된 사이즈보다 크다면
  return findMatryoshka(matryoshka.matryoshka, size)
}	// 내부로 들어가서 탐색하는 재귀함수 선언
 return false
}

---

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

입출력 예시

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) {
  // TODO: 여기에 코드를 작성합니다.

 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) // 그 인자를 인풋으로 받아 재귀 함수로 다시 탐색하는 변수 result

     if(result){ 	// result에서 값이 매칭되면
       return true 	// 트루 리턴
     }
   }
 }
 return false
}
 

---

< 15. 다차원 배열을 입력받아 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]

정답

function flattenArr(arr) {
  // TODO: 여기에 코드를 작성합니다.
if(arr.length === 0){
  return []
}
 else {

   const head = arr[0]		// 배열의 첫번째 인자를 추출
   const tail = arr.slice(1)	// 첫번째 제외한 나머지 인자 추출

   if(Array.isArray(head)){		// 추출한 첫번째 인자가 배열이라면
     return flattenArr([...head, ...tail])
   }		// 모두 전개하여 배열 안의 배열들을 벗겨낸다

   else {	// 배열이 아니라면 
     return [head].concat(flattenArr(tail)) // 첫번째 인자에 이어붙인다. 하나하나씩 검사해서 붙일 수 있게 재귀함수를 이용한다.
   }
 }
}