[Algorithm] 재귀 알고리즘 (Recursion Algorithm)

🔍 재귀 알고리즘이란?

재귀 알고리즘은 문제를 자신과 똑같은 작은 문제로 나누어 해결하는 프로그래밍 기법이다. 어떤 함수가 자신을 다시 호출하여 문제를 해결하는 방식으로 동작한다.

재귀는 마치 “러시아 인형 놀이“와 비슷하다.
큰 인형 안에 작은 인형이 계속 들어있고, 그 안에 또 다른 인형이 있는 것처럼, 함수도 자기 자신을 계속 호출하며 문제를 점차 더 작은 단위로 나누어 해결해 나간다.

---

🧩 재귀 알고리즘의 핵심 구성 요소

재귀 알고리즘이 잘 작동하려면 두 가지 중요한 요소가 필요하다.

1. 기본 조건 (Base Case)

   • 재귀 함수가 언제 멈춰야 하는지를 정의하는 부분이다.
   • 이 조건에 도달하면 더 이상 재귀적으로 자기 자신을 호출하지 않고, 직접 결과를 반환한다.

2. 재귀 조건 (Recursive Case)

   • 문제를 더 작은 문제로 나누는 과정이다.
   • 함수는 자기 자신을 호출하면서 문제를 점점 단순화한다.
   • 마치 큰 문제를 쪼개고 쪼개서 결국 기본 조건에 도달하도록 만드는 단계이다.

러시아 인형으로 보자면,
각 인형 속에는 더 작은 인형이 들어 있다 (재귀 조건).
인형은 점점 작아지다가 결국 가장 작은 인형만 남는다 (기본 조건).

---

🌟 재귀 알고리즘의 특징

1. 문제 분할

   • 복잡한 문제를 더 작고 간단한 부분 문제로 나눈다.
   • 각 부분 문제는 원래 문제와 유사한 구조를 가진다.

2. 메모리 사용

   • 함수 호출마다 새로운 메모리 스택을 사용한다.
   • 깊이가 깊어질수록 메모리 사용량이 증가한다.

3. 가독성

   • 반복문에 비해 코드가 간결하고 직관적일 수 있다.
   • 수학적 귀납법과 유사한 로직 구현에 유용하다.

---

💡 재귀, 언제 사용할까?

그렇다면 재귀 알고리즘은 어떤 상황에서 특히 유용할까?
다음과 같은 경우에 재귀를 사용하면 코드가 더 직관적이고 간결하게 작성될 수 있다.

• 문제를 작은 단위로 나눌 수 있을 때
• 트리 구조 데이터 처리
• 알고리즘 문제 해결
• 수학적 계산

---

✨ 재귀 알고리즘 예제

1. 팩토리얼 계산

주어진 정수 n에 대해, n! (n 팩토리얼)을 계산하는 문제이다.

팩토리얼은 1부터 n까지 모든 정수를 곱한 값이다.

function factorial(n) {
  // 기본 조건: 0! 또는 1!은 1
  if (n <= 1) return 1;

  // 재귀 조건: n! = n * (n-1)!
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 결과: 120

• 기본 조건: n이 1 이하일 경우 1을 반환한다. (0! = 1과 1! = 1)
• 재귀 조건: n!은 n * (n-1)!이므로, 함수는 자신을 계속 호출하여 n에서 1까지 곱해간다.

2. 피보나치 수열

주어진 정수 n에 대해, n번째 피보나치 수를 구하는 문제이다.

피보나치 수열은 각 항이 이전 두 항의 합으로 이루어진 수열이다.

function fibonacci(n) {
  // 기본 조건: 0번째와 1번째 피보나치 수
  if (n <= 1) return n;

  // 재귀 조건: F(n) = F(n-1) + F(n-2)
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(6)); // 결과: 8

• 기본 조건: n이 0 또는 1일 경우 n 자체를 반환한다. 즉, fibonacci(0)은 0, fibonacci(1)은 1을 반환한다.
• 재귀 조건: 피보나치 수열의 정의에 따라, F(n)은 F(n-1)과 F(n-2)의 합이다. fibonacci(6)은 fibonacci(5) + fibonacci(4)를 호출하고, 이 과정이 계속해서 반복된다.

---

⚠️ 재귀 사용 시 유의사항

1. 스택 오버플로우

   • 재귀 깊이가 너무 깊으면 메모리 초과 위험이 있다.
   • 꼬리 재귀 최적화나 반복문으로 대체 가능하다.

2. 성능 고려

   • 중복 계산으로 인한 성능 저하 가능성이 있다.
   • 메모이제이션(Memoization) 기법을 사용하여 이미 계산한 값을 저장하고 재사용할 수 있다.
   • 동적 계획법(Dynamic Programming)을 활용하여 중복 계산을 줄이고 성능을 개선할 수 있다.

3. 종료 조건 필수

   • 재귀 함수에서 명확한 종료 조건이 없으면 무한 재귀에 빠질 수 있다.
   • 종료 조건을 반드시 설정하고, 그 조건에 도달했을 때 함수를 종료하도록 해야 한다.

---

재귀는 강력하고 유용한 도구지만, 사용 시에는 신중하게 설계해야 한다.

적절한 종료 조건을 설정하고, 성능을 고려하여 문제를 해결한다면, 재귀는 효율적이고 깔끔한 코드를 작성할 수 있는 좋은 방법이 될 것이다.