재귀적 정의(Recursive definition)는 수학·논리학·컴퓨터 과학 등에서 사용되는 정의 방법으로, 어떤 객체나 개념을 그 자체 또는 동일한 방법으로 정의된 더 작은 경우에 대한 정의를 통해 기술한다. 즉, 대상의 정의에 스스로를 포함시켜 정의함으로써, 기본 사례(base case)와 재귀 단계(recursive step)를 명시한다.
주요 요소
-
기본 사례(Base case)
- 재귀적 정의가 종료되는 최소 단위의 명시. 예를 들어, 자연수 집합 ℕ을 재귀적으로 정의할 때는 0을 기본 사례로 설정한다.
-
재귀 단계(Recursive step)
- 이전 단계에서 정의된 객체를 이용해 새로운 객체를 정의하는 규칙. 예를 들어, n이 자연수라면 n+1도 자연수라는 식으로 정의한다.
적용 예시
-
자연수 정의:
- 기본 사례: 0은 자연수이다.
- 재귀 단계: n이 자연수이면, n+1도 자연수이다.
-
피보나치 수열:
- 기본 사례: F₀ = 0, F₁ = 1.
- 재귀 단계: n ≥ 2에 대해 Fₙ = Fₙ₋₁ + Fₙ₋₂.
-
리스트 구조:
- 기본 사례: 빈 리스트는 리스트이다.
- 재귀 단계: 원소 a와 리스트 L이 주어지면, [a] + L 역시 리스트이다.
어원 및 언어적 배경
- 재귀적은 한자어 ‘遞歸(재귀)’에서 파생되었으며, ‘이어 가며 돌아가다’라는 의미를 내포한다.
- 정의는 ‘어떤 개념이나 용어의 의미를 명확히 규정하는 행위’를 가리킨다.
- 따라서 ‘재귀적 정의’는 “그 자체를 반복적으로 사용하여 의미를 규정하는 행위”라는 의미로 해석된다.
학문적 의의
재귀적 정의는 복잡한 구조를 단순하고 명확하게 표현할 수 있게 함으로써, 형식 체계와 알고리즘 설계, 프로그래밍 언어의 문법 정의 등에 필수적인 도구로 활용된다. 기본 사례와 재귀 단계가 정확히 규정되지 않으면 정의가 무한히 진행될 위험이 있어, 정의의 완전성과 정당성을 확보하기 위한 엄격한 형식 검증이 요구된다.
