[알고리즘] 재귀 (recursion)

- 들어가며 

오늘은 재귀(recursion)에 대해서 정리하고자 한다.

 

- 재귀란?

재귀함수 : 자기 자신을 호출하는 함수 

   ->재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

 

따라서 문제를 해결하는 과정에서 문제의 과정을 더 쪼개질 수 없을 만큼 작은 단위로 쪼개는 과정이 필요하다.

특히나,

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우 

2. 중첩된 반복문이 많거나 반복문의 중첩 횟수를 예측하기 어려운 경우 

에서 매우 적합 

- 재귀적 사고하기 

1. 재귀함수의 입력값과 출력값 정의하기 

2. 문제를 가장 작은 단위(base case)로쪼개고 경우의 수를 구하기

3. 단순한 문제 해결 

4. 복잡한 문제 해결 

 

즉 핵심은 재귀함수를 base case와 recursive case로 나누는 것.

-base case (재귀의 기초) : 쪼갠 후 가장 해결하기 쉬운 문제 -> 즉, base case는 더이상 안쪼개지는 상황 = 곧 탈출조건임

-recursive case : base case가 아닌 문제

 

 

재귀 함수 탬플릿 

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

  // recursive case : 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

 

---

재귀예시 

팩토리얼

function fact(num){ //팩토리얼 함수 재귀로 표현
	if (n===1){
    	return 1}
    
    return num *fact(num-1)
}

 

피보나치 

function fibonacci(num) {
  if (num===0){
    return 0
  }
  if(num ===1){
    return 1
  }

  //피보나치 2 는 0번째 + 1 번째 
  // 작은수부터 순서대로 더해가야 함 
  //만약 num이 1부터 시작하면 f(n-1)+f(n)
  
  return fibonacci(num-1)+ fibonacci(num-2) 
  // 맨 아랫단 값 정해주고 재귀로 숫자 내리면 베이스로 내려와서 값 찾는순간 윗단까지 전부 계산됨 


}

 

 

 

---

상자속에 선물찾기 

arr 속에 선물 담겨있고 arr이 중첩되어 있어서 내부의 arr까지 내가 원하는 선물인 'wish'와 일치하는 선물이 있는지 확인해야함 

 

function unpackGiftbox(giftBox, wish) {
  //반복문 돌려서 선물 하나씩 체크 
  for( let i of giftBox){
    //내가 찾는 선물인가? -> true 
    if( i ===wish){return true}
    //더 작은 상자 나왔다 -> 재귀 
    if( Array.isArray(i)===true){
    	// 만약 상자 깠는데 wish가 없다고 return false하면 안됨, 끝까지 아직 확인 안했으니까
        // -> true 일때만 리턴하자! 
      if( unpackGiftbox(i,wish)===true){
        return true
      }
    }
  } 
  return false
//반복문 다 돌았는디 내가 찾는 선물이 끝까지 안나왔어 .. -> false리턴

}

 -> 이처럼 박스가 몇겹인지 알 수 없는 , 반복문으로 해결하기 곤란하고 재귀를 반드시 사용해야 풀리는 상황이 있다 

 

 

FlattenArr( arr 안에 있는 모든 arr 제거하고 flatten하게 만들기 = Array mthod flat()

function flattenArr(arr) {
  
  // 반복문 돌리면서 arr나오면 앞뒤로 나누고, 이후에 스프레드로 붙인다. ->recursive case
  for (let i=0; i<arr.length ; i++){
    if(Array.isArray(arr[i])){
      let front= arr.slice(0,i)
      let center= arr[i]
      let right = arr.slice(i+1,arr.length)
      let newArr= [...front,...center,...right] //spread로 붙이면 []풀려서 붙는 것 이용
      return flattenArr(newArr)
    }
  }
  //더 풀어줄 arr 없음 // base case
  return arr

}