[코드스테이츠]-재귀함수

코풀릿 문제를 풀며 배운 내용 복습해보기✨

1. factorial

factorial
문제
수를 입력받아 n-factorial(n!; 엔-팩토리얼) 값을 리턴해야 합니다. n! 은 1부터 n까지 1씩 증가한 모든 값의 곱입니다.
주의 사항
함수 factorial은 재귀함수의 형태로 작성합니다.
반복문(for, while) 사용은 금지됩니다.
factorial(0)은 1로 정의됩니다.
음수 입력은 들어오지 않습니다.
입출력 예시

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

factorial을 계산하는 방법!
factorial(1) = 1
factorial(2) = 1 x 2 = 2
factorial(3) = 1 x 2 x 3 = 6
factorial(4) = 1 x 2 x 3 x 4 = 24

💡작성 코드

function factorial(num) {
  // base case
  if(num === 0){
    return 1
  }
  // recursive case
 return num * factorial(num-1)
}

💡해석

• 주의 사항을 보면 factorial(0) = 1로 정의하기 때문에 base case로 if문을 작성해주고 재귀함수를 사용할 부분은 recursive case로 작성해준다.

2. fibonacci

문제
수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야 합니다.
0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
출력
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 === 0) {
    return 0;
  } else if (num === 1) {
    return 1;
  }
  // recursive case
  if(num > 1) {
    return fibonacci(num - 1) + fibonacci(num - 2);
  }
}

💡해석

• 피보나치 수열은 첫째 항이 0, 둘째 항이 1로 정의될 수 있기 때문에 base case에는 0과 1일 때를 작성해준다.
• 그 뒤의 모든 항은 바로 앞 두 항의 합을 의미한다.
• 즉, 피보나치의 식을 살펴보자면 F(n) = F(n-1) + F(n-2)이다. recursive case에 이 식을 활용하여 재귀함수를 적용할 수 있다.

3.unpackGiftbox

문제
선물 상자에 대한 정보를 담은 배열과 문자열을 입력받아 조건에 맞는 선물이 있는지 여부를 리턴해야 합니다.
출력
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){
   if(gift === wish) {
    return true
  }
  if(Array.isArray(gift)){
    if (unpackGiftbox(gift,wish) === true) {
    return true
      }
    }
  }
   return false
}

💡해석

• unpackGiftbox는 [str], str 모두 boolean값이어야 한다.
• for문을 활용하여 giftbox의 값을 읽은 후 gift에 wish의 값이 있으면 true를 리턴한다.
• 입력받은 값이 배열일 때 재귀함수를 호출한다.