D-40

🔍 재귀함수란?

재귀란 원래의 자리로 되돌아온다는 뜻으로 재귀함수(Recursive Function)는 자기 자신을 부르는 함수다.

비유하면 마트료시카, 엘리베이터 거울에 비치는 거울, 인셉션의 꿈속에 꿈속에 꿈 정도로 이해했다.

재귀함수를 코드로 표현하면 다음과 같다.

function recursion () {
  console.log("This is")
  console.log("recursion!")
  recursion()
}

이 함수를 호출하면 아래와 같은 결과를 볼 수 있다.

함수 자기 자신을 끝없이 호출하며 같은 코드가 실행되는 것을 확인할 수 있다.
이를 통해 재귀함수는 종료조건을 설정하지 않으면 무한 반복을 하는 것을 알 수 있다.

💡 재귀를 사용하기 적합한 상황

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

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

반복문으로 작성된 코드를 더욱 간결하고 이해하기 쉽게 작성하고 싶은 경우

---

📌 재귀함수 템플릿

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

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

---

👨‍🏫 코플릿 예제

1. sumTo

function sumTo(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  if (num === 0) {
    return 0;
  }
  return num + sumTo(num - 1); //sumTo(n)은 자연수 1부터 n까지의 합을 계산하는 함수
}

문제

수(num)을 입력받아 1부터 num까지의 합을 리턴해야한다.

입력

num = number 타입의 정수

출력

number 타입 리턴 (1 + 2 + ... + num)

주의사항

반복문 사용은 금지하며 함수 sumTo는 재귀함수의 형태로 작성한다.

음수 입력은 들어오지 않는다.

---

3. factorial

function factorial(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  if (num <= 1) {
    return 1;
  }

  if (num > 1) {
    return num * factorial(num - 1);
  }
}

문제

수를 입력받아 n-factorial(n!; 엔-팩토리얼) 값을 리턴해야한다.

입력

num = number 타입의 정수 (num >= 0)

출력

number 타입 리턴 (1 * 2 * ... * num)

주의사항

반복문 사용은 금지하며 함수 factorial은 재귀함수의 형태로 작성한다.

음수 입력은 들어오지 않는다.

factorial(0)은 1로 정의한다.

---

4. fibonacci

function fibonacci(num) {
  // TODO: 여기에 코드를 작성합니다.
  // 별도의 최적화 기법(memoization)은 금지됩니다.
  if (num <= 1) {
    return num;
  }
  return fibonacci(num - 1) + fibonacci(num - 2);
}

문제

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

입력

num = number 타입의 정수 (num은 0 이상 15 이하의 정수)

출력

number 타입 리턴 (num 번째 피보나치 수)

주의사항

반복문 사용은 금지하며 함수 fibonacci은 재귀함수의 형태로 작성한다.

피보나치 수열은 0번부터 시작한다.

---

📚 정리

재귀함수는 자기 자신을 부르는 함수다.

재귀함수는 종료조건을 설정하지 않으면 무한 반복한다.

재귀함수는 반복문(for, while)으로도 사용할 수 있다. 하지만 재귀함수를 사용해 코드를 조금 더 간결하게 구현할 수 있다.