📌 재귀(Recursion)란?

알고리즘을 공부하면서 자주 등장하는 개념 중 하나인 재귀 호출에 간단하게 대해 정리해보자.

재귀(Recursion)란

👉 함수가 자기 자신을 다시 호출하는 방식을 의미한다.

재귀의 핵심 구조

재귀 함수는 반드시 아래 두 가지 요소를 포함해야 한다.

• 종료 조건 (Base Case)
  재귀 호출을 멈추는 조건
  이 조건이 없으면 무한 호출이 발생한다 (Stack Overflow)

• 재귀 호출 (Recursive Call)
  문제를 더 작은 단위로 나누어 자기 자신을 다시 호출
  📌 예시: 팩토리얼(Factorial)

---

팩토리얼은 재귀를 이해하기 가장 좋은 예시이다.

def factorial(n):
    if n == 1:  # 종료 조건
        return 1
    return n * factorial(n-1)  # 재귀 호출
    

🔍 동작 과정
factorial(4)
= 4 factorial(3)
= 4 3 factorial(2)
= 4 3 2 factorial(1)
= 4 3 2 * 1
= 24

📌 재귀를 사용하는 이유

재귀는 문제를 같은 형태의 더 작은 문제로 분할할 수 있을 때 매우 강력하다.

특히 아래와 같은 상황에서 많이 사용된다.

트리 구조 탐색 (DFS)
그래프 탐색
백트래킹 (모든 경우의 수 탐색)
분할 정복 (퀵 정렬, 병합 정렬)