알고리즘 재귀 문제 복습

아직은 생소한, 재귀함수를 작성하는 부분을 몇 문제 재복습하며 익히기로 했다.

 

04. 피보나치 수열

수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴해야 합니다.

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1입니다. 그 다음 2번째 피보나치 수부터는 바로 직전의 두 피보나치 수의 합으로 정의합니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

• 함수 fibonacci는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 피보나치 수열은 0번부터 시작합니다.

function fibonacci(num) {
  if(num===0){
    return 0;
  }
  if(num===1){
    return 1;
  }
  return fibonacci(num-1)+fibonacci(num-2)
}

수도 코드:

피보나치 수열은 0부터 시작한다. 피보나치의 규칙은 그 전전의 수+ 그 전의 수.
  //fibonacci(num-2) + fibonacci(num-1)
  //fibonacci(0) === 0;
  //fibonacci(1) === 1;
  //fibonacci(2) === fibonacci(1) + fibonacci(0) = 1; ...

 

 

08. drop

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

• 함수 drop은 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용은 금지됩니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• num과 arr.length 중 최소값만큼 제거합니다.

function drop(num, arr) {
  if(num===0){
  return arr;
} 
  if (arr.length === 0){
    return [];
  }
  const tail = arr.slice(1);
  return drop(num-1, tail);
}

수도 코드: 

초기의 입력 배열은 바뀌지 않아야 한다.
차례대로 num개의 요소가 제거된 새 배열 리턴
배열에 주목한다. 첫번째를 제거한 배열인 const tail을 사용해볼 것
num이 0일 시에는 arr을 그대로 리턴한다.
빈 배열을 받으면 빈 배열을 리턴한다.

drop함수를 재귀시켜주며, num-1 시켜주고 맨 앞의 값을 뺀 tail 배열을 넣어준다.

 

 

14. 선물 풀기 

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

인자 1 : giftBox

• 문자열, 배열을 요소로 갖는 재귀적으로 정의된 배열 (입출력 예시 참고)
• 문자열은 선물 상자에 들어있는 각 선물의 이름을 의미합니다.
• 배열은 더 작은 선물 상자를 의미합니다.

인자 2 : wish

• string 타입의 문자열

주의 사항

• 함수 unpackGiftbox는 재귀함수의 형태로 작성합니다.
• 반복문(for, while) 사용이 가능합니다.
• 입력받은 배열은 함수의 호출 뒤에도 처음 상태를 유지해야 합니다(immutability).
• 빈 배열 또는 빈 문자열을 입력받은 경우, false를 리턴해야 합니다.

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;
}

수도 코드:

 

 

for of문을 써서 gift === wish 인 경우를 구한다.(true)

만약에 gift가 배열일 경우, 재귀함수를 한번 호출하고,

그 내부에 찾던 게 있는 경우(위에서 조건을 걸어준 gift === wish)

마저 true를 리턴한다.