재귀적 정의와 구조적 귀납법

요약

끝없이 많은 대상을 “기본 재료 몇 개”와 “이미 만든 것으로 새것을 만드는 규칙”으로 정의하는 방법이다. 리스트, 트리, 수식, 프로그래밍 언어의 문법이 모두 이렇게 정의되고, 재귀 함수가 이 정의를 그대로 따라간다. 이렇게 정의한 대상의 성질은 같은 모양으로 증명한다. 기본 재료에서 맞고 규칙이 성질을 보존하면 모든 대상에서 맞는다(구조적 귀납법). 단, “이 규칙으로 만든 것만 해당한다”는 조건이 있어야 대상이 딱 정해진다.

예시로 보기

괄호가 제대로 짝지어진 문자열(균형 괄호)을 세 규칙으로 정의한다.

빈 문자열 \(\varepsilon\)은 균형 괄호다.
\(s\)가 균형 괄호면 \((s)\)도 균형 괄호다.
\(s\), \(t\)가 균형 괄호면 이어 붙인 \(st\)도 균형 괄호다.
이 규칙으로 만든 것만 균형 괄호다.

\(\varepsilon \to ()\) (규칙 2) \(\to ()()\) (규칙 3) \(\to (()())\) (규칙 2)처럼 만든다. 길이 6인 균형 괄호는 ((())), (()()), (())(), ()(()), ()()() 다섯 개다. 규칙 1이 아래 정의의 기저, 규칙 2와 3이 생성 규칙, 규칙 4가 한정 조건이다.

정의

집합 \(S\)의 재귀적 정의는 세 부분으로 된다¹.

기저: \(S\)에 속하는 기본 원소들
생성 규칙: \(S\)의 원소들로 \(S\)의 새 원소를 만드는 규칙
한정: 기저에서 규칙을 유한 번 적용해 얻은 것만 \(S\)의 원소다

구조적 귀납법. \(S\)의 모든 원소가 성질 \(P\)를 가짐을 보이려면 (1) 모든 기저 원소가 \(P\)를 가지고 (2) 각 생성 규칙이 \(P\)를 가진 원소들로부터 \(P\)를 가진 원소를 만든다는 것을 보이면 된다.

구조적 귀납법은 “만드는 데 쓴 규칙의 횟수”에 대한 강한 귀납법이라 수학적 귀납법과 같은 근거로 옳다.

재귀 함수. 재귀적으로 정의된 대상 위의 함수는 경우를 나눠 정의한다. 정 이진 트리(full binary tree, 각 노드가 자식 0개 또는 2개)를 “잎 하나” 또는 “왼쪽·오른쪽 트리를 붙인 노드”로 정의하면, 잎의 수는 \(\text{leaves}(\text{잎}) = 1\), \(\ \text{leaves}(T_L, T_R) = \text{leaves}(T_L) + \text{leaves}(T_R)\)이다. 코드도 같은 모양이다.

flowchart TD
  R["새 노드: 내부 노드"] --> L["T_L의 뿌리: 내부 노드"]
  R --> RR["T_R: 잎 하나"]
  L --> L1["잎"]
  L --> L2["잎"]

왼쪽 트리 \(T_L\)(내부 노드 1, 잎 2)과 오른쪽 트리 \(T_R\)(잎 하나)을 새 노드 아래에 붙였다. 생성 규칙을 한 번 쓴 결과이고, 붙인 트리는 잎 3, 내부 노드 2다².

def leaves(t):
    if t is None:               # 잎
        return 1
    left, right = t             # 노드 = (왼쪽, 오른쪽)
    return leaves(left) + leaves(right)

예제

정 이진 트리의 잎은 내부 노드보다 하나 많다.

성질: \(P(T)\): \(\text{leaves}(T) = \text{internal}(T) + 1\).
기저: 잎 하나짜리 트리는 잎 1, 내부 노드 0이라 맞는다.
생성 규칙: \(T_L\), \(T_R\)이 \(P\)를 가진다고 하자. 둘을 새 노드로 붙인 \(T\)는 잎이 \(\text{leaves}(T_L) + \text{leaves}(T_R) = (\text{internal}(T_L) + 1) + (\text{internal}(T_R) + 1)\)개, 내부 노드가 \(\text{internal}(T_L) + \text{internal}(T_R) + 1\)개(새 노드 포함)다. 잎이 내부 노드보다 1 많다.
결론: 모든 정 이진 트리가 \(P\)를 가진다.

검증: 규칙으로 만든 문자열이 길이 12 이하의 모든 균형 문자열과 같음, 개수 1, 1, 2, 5, 14, 42, 132, 무작위 트리 3,000개에서 잎 = 내부 + 1, 순진한 피보나치 재귀의 호출 수 — 13_recursive-definitions_verify.py

활용

자료구조. 연결 리스트(“빈 리스트, 또는 원소 하나와 리스트”), 트리, JSON 값이 재귀 자료형이다. 이런 자료를 다루는 함수는 기저 경우와 재귀 경우로 나뉘는 재귀 함수가 자연스럽다.
문법과 파서. 프로그래밍 언어의 문법(BNF)은 식·문장을 재귀적으로 정의한다. 파서는 이 정의를 따라 재귀적으로 내려간다.
재귀의 비용. 피보나치 수를 정의 그대로 fib(n-1) + fib(n-2)로 계산하면 같은 값을 반복 계산해 호출이 \(2F_{n+1} - 1\)번(\(F\)는 피보나치 수)으로 지수적으로 늘어난다. 정의는 재귀여도 계산은 앞에서부터 쌓아 올리면(동적 계획법) \(n\)번으로 끝난다.
길이 \(2n\)인 균형 괄호의 수 \(1, 1, 2, 5, 14, 42, \dots\)는 카탈랑 수로, 이진 트리의 모양 수 등 여러 곳에 나온다³.
알고리즘에서: 재귀 함수를 짜는 순서(기저 사례부터 보고, 더 작은 같은 문제로 줄이고, 작은 문제의 답은 맞다고 믿기)와 파이썬의 재귀 깊이 한도(약 1,000)는 재귀와 백트래킹에 있다. 균형 괄호는 스택으로 판정하고, 올바른 괄호의 갯수에서는 맨 앞 (와 그 짝으로 나눈 점화식으로 센다. “뿌리 → 오른쪽 → 왼쪽” 순서로 적은 목록을 뒤집으면 후위 순회가 된다는 것도 이진 트리에 대한 구조적 귀납법으로 보인다(길 찾기 게임). 그 밖에 트리 순회와 이진 탐색 트리, 동적 계획법, 4단 고음, 사칙연산에서도 쓴다.

연결

선수: 수학적 귀납법, 집합
이어지는 개념: 선형 점화식(재귀적으로 정의된 수열), 트리

과목별 관점

컴파일러 (3-2학기). 프로그래밍 언어의 문법을 적는 문맥 자유 문법이 재귀적 정의를 화살표로 쓴 것이다. 여는 괄호 \(n\)개 뒤에 닫는 괄호 \(n\)개가 오는 문자열은 \(BALANCED \to (\,BALANCED\,) \mid \epsilon\) 한 줄로 적는다. 이 문서의 말로 옮기면 다음과 같다⁴.

재귀적 정의	문맥 자유 문법
정의하려는 집합의 이름	비단말 기호 (\(BALANCED\))
기저	오른쪽에 자기 자신이 없는 규칙 (\(BALANCED \to \epsilon\))
생성 규칙	오른쪽에 자기 자신이 다시 나오는 규칙 (\(BALANCED \to (\,BALANCED\,)\))
한정(“이렇게 만든 것만”)	시작 기호에서 규칙을 유한 번 써서 만든 문자열만 그 문법의 언어다
구조적 귀납법	규칙을 쓴 횟수(유도의 걸음 수)에 대한 귀납법

이 한 줄 문법에는 이 문서의 규칙 3(이어 붙이기)이 없다. 그래서 (())는 만들지만 ()()는 못 만든다. 세 규칙을 다 옮기면 \(B \to (B) \mid BB \mid \epsilon\)이고, 이 문법이 길이 10 이하의 균형 괄호를 빠짐없이 만든다⁴.
규칙 3을 그대로 옮긴 \(B \to BB\)에는 값이 따른다. ()()()를 앞의 둘부터 묶을 수도 뒤의 둘부터 묶을 수도 있어, 문자열 하나에 만드는 과정을 그린 나무가 둘 나온다. 집합을 정의할 때는 “만들 수 있는가”만 중요해서 문제가 없었지만, 컴파일러는 그 나무로 뜻을 정하므로 나무가 하나만 나오게 문법을 고쳐 쓴다(모호한 문법). \(B \to (B)B \mid \epsilon\)은 같은 문자열들을 만들면서 나무가 늘 하나다⁴.
위 ‘활용’에서 “파서는 이 정의를 따라 재귀적으로 내려간다”고 한 것이 재귀 하강 파싱이다. 문법의 규칙 하나가 재귀 함수의 경우 하나가 된다.

확인 문제

C1 균형 괄호의 재귀적 정의(기저 ε, 규칙 (s)와 st)를 쓰고, 길이 6인 균형 괄호를 모두 나열하라.

답: 기저 \(\varepsilon\), 규칙 \(s \Rightarrow (s)\), \(s, t \Rightarrow st\), 그리고 이렇게 만든 것만. 길이 6: ((())), (()()), (())(), ()(()), ()()().

C2 정 이진 트리에서 잎 = 내부 노드 + 1을 구조적 귀납법으로 증명하라. 생성 규칙 단계에서 +1은 어디서 오는가?

답: 기저: 잎 하나(1 = 0 + 1). 규칙: \(T_L\), \(T_R\)이 성질을 가지면 붙인 트리의 잎은 \((i_L + 1) + (i_R + 1)\), 내부 노드는 \(i_L + i_R + 1\)이다. 내부 노드의 \(+1\)은 둘을 잇는 새 노드이고, 잎 쪽에는 \(+1\)이 두 번 있어 차이가 1로 유지된다.

C3 “리스트는 빈 리스트이거나, 원소 하나와 리스트의 쌍이다”라는 정의를 따라 리스트의 길이를 구하는 재귀 함수를 쓰라.

답: def length(xs): return 0 if xs is None else 1 + length(xs[1]) (리스트를 (머리, 꼬리) 쌍으로 표현). 기저에서 0, 규칙마다 1을 더한다. 정의의 두 경우가 함수의 두 경우가 된다.

C4 균형 괄호의 세 규칙(기저 ε, 규칙 (s)와 st)을 문맥 자유 문법으로 옮겨라. 한 줄 문법 \(BALANCED \to (BALANCED) \mid \epsilon\)과는 어떤 문자열에서 달라지는가?

답: \(B \to (B) \mid BB \mid \epsilon\). 한 줄 문법에는 이어 붙이기 규칙 \(B \to BB\)가 없어서 ()(), (())()처럼 덩어리가 옆으로 이어진 문자열을 만들지 못한다. 길이 4에서는 (())만, 길이 6에서는 ((()))만 만든다.
이유: 기저가 자기 자신이 없는 규칙, 생성 규칙이 자기 자신이 다시 나오는 규칙이 된다. 규칙 하나를 빼면 만들어지는 집합이 줄어든다.

Lehman·Leighton·Meyer, Mathematics for Computer Science, 7장 “Recursive Data Types”(재귀적 정의, 구조적 귀납법, 균형 괄호). Rosen, Discrete Mathematics and Its Applications 7판, 5장. ↩
‘재귀 함수’ 문단의 정 이진 트리 정의(잎 하나, 또는 두 트리를 붙인 노드)를 작은 예로 그렸다. ↩
\(n\)번째 카탈랑 수는 \(\frac{1}{n+1}\binom{2n}{n}\)이다. 이 값은 검증 코드의 개수와 같다(1, 1, 2, 5, 14, 42, 132). ↩
세 규칙을 옮긴 문법이 길이 10 이하의 균형 괄호를 모두 만드는 것과 한 줄 문법이 그 일부만 만드는 것은 11_context-free-grammar_verify.py로, 나무의 수는 13_ambiguous-grammar_verify.py로 확인했다. ↩ ↩² ↩³