개요

• 재귀의 개념, 재귀의 장점, 재귀의 활용을 알아봅시다.
• 재귀적 사고를 연습하고 익숙해집시다.
  • 재귀로 문제 해결하는 방법
  • 재귀의 base case(기초)
  • 재귀의 탈출 조건
  • 재귀 함수의 base case 와 recursive case

자전거 처음 탈때처럼 자연스러워질 때까지 연습해야합니다.

---

재귀의 개념

사전적 정의

• 재귀 : 원래의 자리로 되돌아가거나 되돌아옴.

프로그래밍적 정의

• 재귀함수 : 자기 자신을 호출하는 함수입니다.
• 코드 예시

function recursion () {
  console.log("Hello");
  console.log("Recursion");
  
  rescursion();
}

---

재귀의 장점

반복문 vs 재귀 함수

• 모든 재귀 함수는 반복문으로 표현할 수 있지만, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽습니다.
  • 간결하다는 건 인정, 이해하기 쉽다는 건 저한테는 아직인것 같습니다
  • 재귀가 반복문보다 이해하기 쉽다고 느껴질수 있게 학습하겠습니다!

재귀는 알고리즘의 많은 부분을 차지 하기 때문에 기초를 확실하게 다져두는 게 좋습니다.

---

재귀의 활용

재귀로 문제 해결하기

• 재귀로 문제를 해결하는 단계
  1. 문제를 좀더 작게 쪼갭니다.
  2. 문제가 더 작아지지 않을 떄까지, 원자 단위로 문제를 쪼갭니다.
  3. 원자 단위의 문제를 풂으로써 전체 문제를 해결합니다.

재귀는 언제 사용할까요?

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

---

재귀적 사고

재귀적 사고의 단계

1. 재귀 함수의 입력값과 출력값 정의하기
   • 타입으로 간단하게 정의
   • 노트
     • arrMul : [number] => number

2. 문제를 쪼개고 경우의 수를 나누기
   • 일반적인 경우의 수 나누기
     1. 문제를 더 이상 쪼갤 수 없는 경우
     2. 문제를 연속적으로 쪼갤수 있는 경우
   • 노트
     • arrMul : [number] => number
     • arrMul([])
     • arrMul([요소1, 요소2, ..., 요소n])

3. 단순한 문제 해결하기
   • 재귀의 기초 (base case)
     • 가장 해결하기 쉬운 문제부터 해결
     • 재귀의 탈출 조건 (재귀 호출이 멈추는 조건)
     • 문제를 최대한 작게 쪼갠 후 문제 해결
   • 노트
     • arrMul : [number] => number
     • arrMul([]) === 0
     • arrMul([요소1, 요소2, ..., 요소n])

4. 복잡한 문제 해결하기
   • 남아있는 복잡한 경우를 해결합니다.
     • 배열의 첫 요소와 문제를 쪼개는 방법, 문제 해결능력만 있으면 함수를 재귀적으로 구현할 수 있습니다.
   • 노트
     • arrMul : [number] => number
     • arrMul([]) === 0
     • arrMul([요소1, 요소2, ..., 요소n]) === 요소1 * arrMul([요소2, ..., 요소n])

5. 코드 구현

   • 재귀적 사고 단계를 거쳐 쪼개고 해결한 것들을 코드로 구현합니다.

     
     function arrMul(arr:number):number {
       // base case : 문제를 더 이상 쪼갤 수 없는 경우
       if (arr.length === 0) return 1;
       
       // recursive case : 문제를 연속적으로 쪼갤 수 있는 경우
       return arr.shift() * arrMul(arr);
     }
     
     console.log(arrMul([1, 2, 3, 4])); // 24

---

팩토리얼 구현하기 (TypeScript)

1. 입력값과 출력값 정의

• 노트

fac : number => number

2. 문제를 쪼개고 경우의 수를 나누기

• 노트

fac : number => number
fac(1)
fac(5,4,3,2)

3. 단순한 문제 해결하기

fac : number => number
fac(1) === 1
fact(5,4,3,2)

4. 복잡한 문제 해결하기

fac : number => number
fac(1) === 1
fact(5,4,3,2) === 5 * fac(5-1)

5. 코드구현 (TypeScript)

• 함수 선언식

function fac(num: number):number {
  // TODO
  if (num === 1) return 1;
  
  return num * fac(num-1);
}

console.log(fac(5)); // 120

• 함수 표현식

const fac = function(num: number):number {
  // TODO
  if (num === 1) return 1;
  
  return num * fac(num-1);
}

console.log(fac(5)); // 120

• 화살표 함수

const fac = (num: number):number => {
  // TODO
  if (num === 1) return 1;
  
  return num * fac(num-1);
}

console.log(fac(5)); // 120

---

덧붙임

• 재귀 재밌습니다. 아직 익숙하지 않은데 재귀적, 원자적사고 하는 습관을 들이면서 익숙해 지겠습니다.
• 익숙해진 후 알고리즘이나 개발시에 사용하면 코드가 더 깔끔해지고 좋을 것 같습니다.
• 타입스크립트로 재귀함수를 처음 구현해봤는데 출력값의 타입을 지정해주라는 에러를 처음 봐서 덕분에 함수 출력값의 타입 지정하는 방법도 같이 공부할 수 있었습니다.

---

참조

코드스테이츠 프론트엔드 부트캠프
타입스크립트 공식문서