[TIL] 재귀

재귀 함수

재귀 함수는 자기 자신을 호출하는 함수를 말한다.

• 재귀로 문제를 해결하기 위한 과정
  : 문제 작게 쪼개기 => 가장 작은 단위로 쪼개기 => 가장 작은 단위 문제 풂으로써 전체 문제 해결

• 재귀를 사용하는 경우

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있을 때
2. 중첩된 반복문이 많거나 반복문 중첩 횟수 예측이 어려울 때
3. 반복문으로 작성된 코드 더욱 간결하고 이해하기 쉽게 작성하고 싶을 때

• 재귀 함수 탬플릿 (이 모양을 기억하고 문제를 푸니까 조금 수월하긴 했지만 좀 더 어려운 문제나 반복문과 섞어서 푸는 문제들에서는 그래도 어려웠음)

function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

• 팩토리얼 재귀 함수로 풀어보기

문제 : 자연수를 입력받고, 입력받은 수부터 1까지의 자연수를 모두 곱한 값을 리턴하는 재귀 함수 `fac` 을 작성하세요.
  예1) fac(5)  ===  5 * 4 * 3 * 2 * 1  ===  120
  예2) fac(3)  ===  3 * 2 * 1  ===  6

function fac (num) {
  //base case : num이 1일 때
  if(num=1){
    return 1
  }
  
  //recusive case
  return n*fac(n-1)

재귀 과제

isOdd

: 반복문 사용 금지, 나눗셈이나 나머지 연산자(/,%) 사용 금지, 0은 짝수로 간주, 재귀 함수 형태로 작성할 것.(num은 number 타입의 정수)

funcion isOdd(num){
  //base case : num이 0일때와 1일 때 
  if(num === 0){
    return false
  }
  if(num === 1){
    return true
  }
  
  //recursive case
  //나눗셈 연산자 사용이 불가능하므로 계속해서 2를 빼는 방법 사용
  
  //테스트 케이스에 num이 음수인 경우도 있어서 양수로 바꿔줌 
  if(num < 0){
    return isOdd(-num)
  }
  
  return isOdd(num-2)


}

fibonacci

: 반복문 사용 금지, 수 num 입력받아 피보나치 수열의 num번째 요소 리턴, 피보나치 수열은 0부터 시작, 재귀 함수의 형태로 작성.

funcion fibonacci (num){
  //base case : 0번째와 1번째는 자기자신 
  if(num === 0 || num ===1){
    return num
  }
  
  //recursive case : num-1 피보나치 배열과 num-2 피보나치 배열을 더한다 
  return fibonacci(num-1) + fibonacci(num-2)
}

drop

: num(수)와 arr(배열) 입력 받아 차례대로 num개 요소가 제거된 새로운 배열 리턴

function drop(num, arr){
  //base case : num > arr.length 인 경우 
  if(num > arr.length || arr.length === 0){
    return []
  }else if(num === 0){
    return arr
  }
  
  //recursive case : 
  return drop(num-1,arr.slice(1))
}

arr.slice 복습

//MDN 예시 
const animals = ['ant', 'bison', 'camel', 'duck', 'elephant'];

console.log(animals.slice(2));
// expected output: Array ["camel", "duck", "elephant"]

console.log(animals.slice(2, 4));
// expected output: Array ["camel", "duck"]

console.log(animals.slice(1, 5));
// expected output: Array ["bison", "camel", "duck", "elephant"]

console.log(animals.slice(-2));
// expected output: Array ["duck", "elephant"]

console.log(animals.slice(2, -1));
// expected output: Array ["camel", "duck"]

console.log(animals.slice());
// expected output: Array ["ant", "bison", "camel", "duck", "elephant"]

reverseArr

: 입력 받은 배열을 순서가 뒤집힌 배열로 리턴, 재귀 함수 사용, 반복문 금지, 원 배열 immutable, 빈 배열은 빈 배열 그대로 리턴

function reverseArr (arr){
 //base case : arr가 빈 배열일 때 
  if(arr.length === 0){
    return arr
  }
  //recursive case : 맨 뒤 요소를 빈 배열에 담고, 그 뒤에는 재귀와 스프레드 연산자 이용 
  return [arr[arr.length-1],...reverseArr(arr.slice(0,-1))]

findMatryoshka

: 재귀적으로 정의된 객체 (matryoshka, size 속성을 갖는다)와 size 값을 입력 받아 해당 size 값에 해당하는 객체가 존재하는지 boolean 값 반환.

function findMatryoshka (matryoshka, size){
//recursive case 
if(matryoshka.size === size){
  return true
   }else if(matryoshka.size > size && matryoshka.matryoshka){
 return findMatryoshka(matryoshka.matryoshak, size)
}

//base case
return false
}

unpackGiftbox

:선물상자에 대한 정보를 담은 배열과 문자열을 입력 받아 조건에 맞는 선물이 있는지 여부 리턴. 반복문 사용 가능, 재귀함수 사용, 배열 immutable, 빈 배열이나 빈 문자열 false 리턴.

funcion unpackGiftbox (giftbox, wish){
 
  for(let i=0;i<giftbox.length;i++){
   if(giftbox[i] === wish){
     return true
   }else if(Array.isArray(giftbox[i])){
    let result = unpackGiftbox(giftbox[i],wish)
    if(result === true){
      return true
    }
     return fasle  
   } 
  }
}

//다른 풀이 
function unpackGiftbox(giftBox, wish){
  //반복문 돌리면서 요소들 체크
  for(let gift of giftBox){
    //내가 찾는 선물이 있으면 true 리턴
    if(gift === wish){
      return true
    }
    
    //선물 중에 상자가 있으면 재귀 호출
   	if(Array.isArray(gift)){
      if(unpackGiftbox(gift,wish) === true){
        return true
      }
    }
  }
  //반복문 끝나고도 없으면 false 리턴 
  return false
}

flattenArr

: 다차원의 배열을 입력 받아 1차원 배열로 변환 후 리턴. 반복문 사용 가능, 재귀 함수 형태로 작성, 입력 받은 배열 immutable, 빈 배열 입력시 빈 배열 리턴, flat()이나 flatMap() 사용 불가.

function flattenArr (arr){
	let result = []
  for(let i=0;i<arr.length;i++){
  	if(Array.isArray(arr[i])){
      let flat = flattenArr(arr[i]))
      result.push(...flat)
    }else{
      result.push(arr[i])
    }
  }
return result 
}