재귀 (Recursion)

재귀 (Recursion)

함수가 자기 자신을 호출하여 문제를 더 작은 부분 문제로 분해하여 해결하는 알고리즘 기법으로, 기저 조건(Base Case)과 재귀 호출로 구성

목적: 복잡한 문제의 단순화, 분할 정복, 자기 유사 구조 처리

특징: 자기 호출, 기저 조건 필수, 호출 스택 사용, 수학적 귀납법

구조

• •기저 조건(Base Case): 재귀 호출 없이 직접 해결, 종료 조건
• •재귀 조건(Recursive Case): 더 작은 문제로 자기 호출

예시: 팩토리얼

• •기저: factorial(0) = 1
• •재귀: factorial(n) = n × factorial(n-1)

예시: 피보나치

• •기저: fib(0) = 0, fib(1) = 1
• •재귀: fib(n) = fib(n-1) + fib(n-2)

호출 스택: 각 재귀 호출은 스택 프레임 생성, 깊은 재귀는 스택 오버플로우

꼬리 재귀(Tail Recursion)

• •재귀 호출이 함수의 마지막 연산
• •컴파일러가 루프로 최적화 가능 (Tail Call Optimization)
• •스택 공간 O(1)로 감소

장점: 코드 간결, 자연스러운 문제 표현, 트리/그래프 탐색 적합

단점: 스택 오버플로우 위험, 중복 계산(메모이제이션 필요), 성능 오버헤드

적용사례: 분할 정복, 트리 순회, DFS, 하노이 탑, 백트래킹

비교: 재귀(간결/스택위험) vs 반복(복잡/안전) vs 꼬리재귀(최적화가능)

연관: 분할 정복, 스택, 메모이제이션, DP, 백트래킹