재귀
재귀 (Recursion)
재귀(Recursion)는 어떠한 문제를 해결할 때, 그 문제와 구조는 같지만 크기가 더 작은 문제의 결과물을 이용하여 원래의 문제를 해결하는 방식입니다. 프로그래밍에서는 함수가 자기 자신을 다시 호출하는 형태로 구현되며, 복잡한 문제를 간결하고 직관적으로 표현할 수 있게 해줍니다.
🔄 재귀의 구성 요소
모든 재귀 함수는 반드시 두 가지 핵심 요소를 가져야 합니다.
- 기본 사례 (Base Case)
> * '정의': 재귀 호출을 멈추고, 결과를 반환하는 조건입니다. 재귀 함수에서 가장 작은 단위의 문제입니다. > * '중요성': 기본 사례가 없으면 함수가 자기 자신을 무한히 호출하여 '스택 오버플로우(Stack Overflow)' 오류가 발생합니다.
- 재귀 사례 (Recursive Case)
> * '정의': 문제를 더 작은 단위로 쪼개고, 자기 자신을 다시 호출하는 부분입니다. > * '중요성': 재귀 호출을 할 때마다 문제의 크기가 점차 작아져서, 결국 기본 사례에 도달하도록 설계해야 합니다.
👍 재귀의 장점과 단점
- 장점 (Advantages)
> * 간결한 코드 : 복잡한 문제를 매우 간결하고 직관적으로 표현할 수 있습니다. (e.g., 트리 순회, 팩토리얼, 피보나치 수열) > * 문제 분할 용이 : 점화식이나 수학적 귀납법으로 표현되는 문제를 코드로 옮기기 쉽습니다.
- 단점 (Disadvantages)
> * 성능 문제 : 함수 호출에 따른 오버헤드가 발생합니다. 스택 프레임을 생성하고 해제하는 과정에서 반복문에 비해 성능이 느릴 수 있습니다. > * 스택 오버플로우 (Stack Overflow) : 재귀 호출의 깊이가 너무 깊어지면, 함수 호출 스택에 할당된 메모리를 초과하여 프로그램이 비정상적으로 종료될 수 있습니다. > * 디버깅의 어려움 : 반복문에 비해 코드의 실행 흐름을 추적하기 어려울 수 있습니다.
💡 개발자 핵심 Point
- 재귀 vs 반복문 : 모든 재귀 함수는 반복문(스택을 사용하여)으로 변환 가능하며, 그 반대도 가능합니다. 문제의 성격에 따라 더 자연스럽고 가독성 좋은 방법을 선택하는 것이 중요합니다.
- 꼬리 재귀 최적화 (Tail Recursion Optimization)
> * '정의': 재귀 호출이 함수의 가장 마지막에 이루어지는 형태의 재귀입니다. > * '최적화': 일부 컴파일러나 언어(주로 함수형 언어)는 꼬리 재귀를 인식하여, 추가적인 스택 프레임을 생성하는 대신 기존 스택 프레임을 재사용하는 방식으로 최적화합니다. 이를 통해 스택 오버플로우를 방지하고 반복문과 유사한 성능을 낼 수 있습니다.
- 재귀는 깊이 우선 탐색(DFS), 분할 정복(Divide and Conquer), 백트래킹(Backtracking)과 같은 여러 알고리즘 패러다임의 근간을 이룹니다.
- 메모이제이션 (Memoization) : 단순 재귀(e.g., 피보나치 수열)에서 발생하는 중복 계산 문제를 해결하기 위해, 계산된 값을 저장해두고 재사용하는 기법입니다. 동적 계획법(Dynamic Programming)의 핵심 아이디어 중 하나입니다.
