재귀

재귀의 핵심

동일한 구조의 더 작은 문제 해결하기!

반복문이 중첩되고 얼마나 반복되는지 모를 때,
즉 while을 쓰는 문제를 간단하게 표현할 수 있다고 생각하자

재귀적 사고

1. 입출력값 정의
2. 쪼개고 나누기

• 더 큰 경우, 작은 경우의 풀이가 동일한가? : 쪼개기
• 풀이가 다라지는가? : 경우의 수로 나누기
  ❗️ 구조분해할당을 잘 사용해보자

3. 탈출 조건 찾기 : base case(terminating case, 답을 바로 알 수 있는 해결하기 쉬운 문제)를 힌트로 한다.
4. 남은 복잡한 문제 해결하기

재귀의 특징

• 코드가 매우 직관적이다
• 보기에는 직관적이지만 stack overflow 문제가 발생할 수 있다
  : 함수 내에서 다시 함수를 호출하기때문에, 하나의 함수가 실행을 마치지 않은 상태에서 계속 함수를 불러와 스택이 넘쳐버림

꼬리재귀

일반 재귀를 최적화하기 위해서 사용하며 꼬리재귀에서 탈출했을 때만 연산한다.

function factorialTail (num, acc) {
  if(num === 1){
    return acc
  }
  return factorialTail(num - 1, num * acc);
}

function factorial(num) {
  return factorialTail(num, 1)
}

일반 재귀를 사용해 팩토리얼을 나타내면 아래와 같다.

function factorial(num) {
  if(num === 0) {
    return 1;
  }
  return num * factorial(n - 1)
  // num : head, factorial(n - 1) : tail
}