맨위로가기

재귀적 정의

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

재귀적 정의는 어떤 대상을 자기 자신을 사용하여 정의하는 방법으로, 재귀의 기초(base case)와 점화식(recursive step)으로 구성된다. 순환 정의와 달리 재귀적 정의는 자기 자신을 직접 참조하지 않고, 기본 경우를 가지며, 더 단순한 경우를 반복하여 정의한다. 재귀적 정의는 수학, 논리학, 컴퓨터 프로그래밍 등 다양한 분야에서 활용되며, 덧셈, 곱셈, 지수, 소수, 논리식(WFF) 등의 정의에 사용된다. 논리 프로그래밍에서는 재귀적 정의를 논리 프로그램으로 표현하여 문제 해결에 활용한다.

더 읽어볼만한 페이지

  • 정의 (논리학) - 한정 (논리학)
    한정은 철학과 논리학에서 개념에 종차를 더해 종 개념을 만드는 작용이자, 개념의 내포를 늘려 외연을 줄여 개념의 모호성을 없애는 정의의 한 형태로, 아낙시만드로스는 한정된 것은 알케가 될 수 없다고 주장했다.
  • 정의 (논리학) - 외연
    외연은 논리학에서 개념이 적용되는 대상들의 집합을 의미하며, 수학에서는 수학적 개념에 의해 지정된 집합, 형이상학에서는 존재하지 않는 대상의 포함 여부에 대한 논쟁과 관련된 개념이다.
  • 재귀 - 무한 루프
    무한 루프는 컴퓨터 프로그램에서 루프가 종료되지 않고 무한히 반복되는 현상으로, 프로그램 오류나 의도적인 경우에 발생하며 시스템 응답 불능을 초래하거나 특정 상황에서 사용되기도 한다.
  • 재귀 - 점화식
    점화식은 수열의 각 항을 이전 항들의 함수로 표현하는 방정식으로, 피보나치 수열, 로지스틱 맵, 이항 계수 등의 예시가 있으며, 선형대수학이나 Z변환 등을 이용하여 풀고 다양한 분야에 응용된다.
  • 수리논리학 - NAND 게이트
    NAND 게이트는 모든 입력이 1일 때 0을 출력하고 그 외에는 1을 출력하는 논리 게이트로서, 다양한 기호로 표현되며, AND 연산의 결과를 부정하는 연산을 수행하고, 여러 방식으로 구현될 수 있으며, 기능적으로 완전하여 디지털 회로 설계에 필수적이다.
  • 수리논리학 - 셈
    셈은 대상의 개수를 파악하는 기본적인 행위로, 수학에서는 집합의 원소 개수를 파악하는 과정으로 정의되며, 셈의 방식에 따라 결과가 달라질 수 있고, 셈을 배우는 과정은 아동의 교육 및 발달에 중요한 역할을 한다.
재귀적 정의

2. 재귀적 정의의 형태

대부분의 재귀적 정의는 재귀의 기초(첫째항)와 점화식을 갖는다.

재귀적 정의는 논리학이나 컴퓨터 프로그래밍에서 자주 발견된다. 예를 들어 논리식(WFF)은 다음과 같이 정의된다.

1. 명제를 나타내는 기호 '''p''', '''q''' 등은 WFF이다.

2. '''N'''에 WFF가 부착된 것은 WFF이다.

3. 4종류의 논리 연산 ('''C''', '''A''', '''K''', '''E''') 중 하나에, 2개의 WFF가 부착된 것은 WFF이다.

4. 이상에 의해 WFF로 정의되는 것만이 WFF이다.

이러한 재귀적 정의를 사용하여, 어떤 기호열이 논리식인지 여부를 판정할 수 있다.


  • '''Kpq'''는 WFF인 '''p'''와 '''q'''가 '''K'''에 부착된 것이므로, WFF이다.
  • '''NKpq'''는 WFF인 '''Kpq'''가 '''N'''에 부착된 것이므로, WFF이다.
  • '''KNpNq'''는 '''K'''에 '''Np'''와 '''Nq'''가 부착되어 있고, '''Np''' 및 '''Nq'''는 WFF이므로, WFF이다.
  • '''Npq'''는 WFF가 아니다.

2. 1. 순환 정의와의 차이점

순환정의와 재귀적 정의의 차이점은, 재귀적 정의는 항상 ''재귀적 기초''(정의 자체의 관점에서 정의되지 ''않고'' 정의를 충족하는 사례)를 가져야 하며 점화식의 다른 모든 경우는 어떤 의미에서 "더 단순한" 경우로 재귀해야 한다는 것이다.[10][11][2] 순환 정의에는 재귀적 기초가 없을 수 있으며, 함수의 다른 값이 아닌 스스로의 값을 통해서 함수 값을 정의할 수도 있다. 이러한 정의는 무한 회귀로 이어진다.

재귀적 정의가 타당하다는 것(재귀적 정의가 고유한 함수를 가진다는 것)은 재귀정리로 알려진 집합론의 정리이며, 그 증명은 자명하지 않다.[12][3] 함수의 정의역이 자연수인 경우 정의가 타당하기 위한 충분 조건은 ''f''(0)의 값(재귀적 기초)이 주어지고 ''n'' > 0에 대해 n에 관한 함수 ''f''(''n'')가 f(0), f(1), \dots, f(n-1)의 값을 가지는 알고리즘(점화식)이 있어야 한다는 것이다.

좀 더 일반적으로, 함수의 재귀적 정의는 초한재귀 원리를 사용하여 정의역이 잘 정렬된 집합인 경우 만들어질 수 있다. 타당한 재귀적 정의를 만족하는 형식적 기준은 일반적인 경우에 더 복잡하다. 일반적인 증명의 큰 틀과 기준은 제임스 멍크레스의 ''Topology''에서 찾을 수 있다.[13][4]

예시로 소수의 정의를 제시한다:

  • 1은 소수가 아니다.
  • 1이 아닌 정수가 소수라는 것은, 자신보다 작은 어떤 소수로도 나누어 떨어지지 않는 것이다.


정수 1이 이 경우의 기본 케이스이다. 그보다 큰 정수 ''X''가 소수인지 여부를 판정하려면, X와 1 사이의 모든 정수에 대해 소수인지 여부를 알고 있어야 한다. 그러한 정수들은 X보다 기본 케이스인 1에 더 가깝기 때문에, 이 정의는 재귀적 정의로서 유효하다.

대조적으로 순환 정의에는 기본 케이스가 없고, 단순히 자신으로 자신을 정의하고 있을 뿐이다. 이것이 악순환을 낳는다. 따라서 "재귀적 정의: '재귀적 정의'를 참조"라는 기술은 순환 정의이며 재귀적 정의가 아니다.

2. 2. 재귀적 정의의 타당성

재귀적 정의가 타당하다는 것(재귀적 정의가 고유한 함수를 정의한다는 것)은 재귀정리로 알려진 집합론의 정리이며, 그 증명은 자명하지 않다.[12] 함수의 정의역이 자연수인 경우, 정의가 타당하기 위한 충분 조건은 ''f''(0)의 값(재귀적 기초)이 주어지고, ''n'' > 0에 대해 ''n''에 관한 함수 ''f''(''n'')가 f(0), f(1), ..., f(n-1)의 값을 가지는 알고리즘(점화식)이 있어야 한다는 것이다.

좀 더 일반적으로, 함수의 재귀적 정의는 초한재귀 원리를 사용하여 정의역이 잘 정렬된 집합인 경우 만들어질 수 있다. 타당한 재귀적 정의를 만족하는 형식적 기준은 일반적인 경우에 더 복잡하다. 일반적인 증명의 큰 틀과 기준은 제임스 멍크레스의 ''Topology''에서 찾을 수 있다. 일반적인 재귀 정의의 특정한 경우(정의역은 잘 정렬된 집합 대신 양의 정수로 제한되는 경우)는 아래 문단에 나와있다.[13]

2. 3. 재귀적 정의의 원리

집합 ''A''에 대하여 ''a''0를 ''A''의 원소라 하자. ''ρ''를 양의 정수의 비어 있지 않은 부분을 ''A''의 원소인 ''A''에 매핑하는 각 함수 ''f''에 할당하는 함수라고 하면, 다음과 같이 나타나는 유일한 함수 h : \Z_+ \to A가 존재한다.

:\begin{align}

h(1) &= a_0 \\

h(i) &= \rho \left(h|_{\{1,2,\ldots,i-1\}}\right) \text{ for } i>1.

\end{align}

3. 재귀적 정의의 예시

음이 아닌 짝수는 다음과 같이 재귀적으로 정의할 수 있다.


  • 0은 음수가 아닌 짝수 집합의 원소이다.
  • 어떤 수가 음수가 아닌 짝수 집합의 원소이면, 그 수에 2를 더한 값도 해당 집합의 원소이다.
  • 위의 두 조건으로 만들 수 없는 수는 음수가 아닌 짝수 집합의 원소가 아니다.


논리학이나 컴퓨터 프로그래밍에서 재귀적 정의의 예시를 찾을 수 있다. 정형 논리식(WFF)은 다음과 같이 재귀적으로 정의된다.

  • 명제를 나타내는 기호(예: p는 "코너는 변호사다")는 WFF이다.
  • WFF에 부정 기호(예: Np는 "코너는 변호사가 아니다")를 붙인 것은 WFF이다.
  • 두 개의 WFF 사이에 곱, 합 등 네 가지 이진 접속사를 넣어 만든 것(예: Kpq는 "코너는 변호사이고, 메리는 음악을 좋아한다")은 WFF이다.


이러한 정의를 통해 특정 기호열이 논리식인지 판별할 수 있다. 예를 들어, Kpq는 WFF인 p와 q가 K에 부착된 것이므로 WFF이다. NKpq는 WFF인 Kpq가 N에 부착된 것이므로 WFF이다. KNpNq는 K에 Np와 Nq가 부착되어 있고, Np 및 Nq는 WFF이므로 WFF이다.

소수의 집합은 다음 조건을 만족하는 유일한 양의 정수 집합으로 정의될 수 있다.

  • 1은 소수가 아니다.
  • 2는 소수이다.
  • 다른 양의 정수는 그보다 작은 소수로 나누어 떨어지지 않을 때 소수이다.

3. 1. 초등 함수

덧셈은 셈을 통해 다음과 같이 재귀적으로 정의된다.

:\begin{align}

& 0 + a = a, \\

& (1+n) + a = 1 + (n+a).

\end{align}

곱셈은 다음과 같이 재귀적으로 정의된다.

:\begin{align}

& 0 \cdot a = 0, \\

& (1+n) \cdot a = a + n \cdot a.

\end{align}

지수는 다음과 같이 재귀적으로 정의된다.

:\begin{align}

& a^0 = 1, \\

& a^{1+n} = a \cdot a^n.

\end{align}

이항 계수는 다음과 같이 재귀적으로 정의할 수 있다.

:\begin{align}

& \binom{a}{0} = 1, \\

& \binom{1+a}{1+n} = \frac{(1+a)\binom{a}{n}}{1+n}.

\end{align}

3. 2. 소수

소수의 집합은 다음을 만족하는 유일한 양의 정수 집합으로 정의될 수 있다.

  • 1은 소수이다.
  • 다른 양의 정수는 자신보다 작은 1이 아닌 소수들로 나누어지지 않을 때만 소수이다.


정수 1은 소수의 재귀적 기초다. 이 정의에 따라 더 큰 정수 ''X''의 소수성을 확인하려면 1과 ''X'' 사이의 모든 정수의 소수성을 알아야 하며, 이는 이 정의에 의해 잘 정의된다.

소수 집합은 다음을 만족하는 고유한 양의 정수 집합으로도 정의할 수 있다.

  • 2는 소수이다.
  • 다른 모든 양의 정수는 그보다 작은 소수로 나누어 떨어지지 않을 때 소수이다.


정수 2의 소수 여부는 기본 사례이다. 이 정의에 따라 ''X''인 모든 더 큰 정수의 소수 여부를 확인하려면 2에서 ''X'' 사이의 모든 정수의 소수 여부를 알아야 한다. 이는 이 정의에 의해 잘 정의되어 있다.

3. 3. 음이 아닌 짝수


  • 0은 음수가 아닌 짝수의 집합 의 원소이다.
  • 집합 의 임의의 원소 에 대해 는 의 원소이다.
  • 위 두 조건으로 얻어지지 않는 것은 의 원소가 아니다.

3. 4. 정형 논리식 (Well-Formed Formula, WFF)

논리학이나 컴퓨터 프로그래밍에서 재귀적 정의를 자주 찾아볼 수 있다. 예를 들어, 정형 논리식(wff)은 다음과 같이 정의될 수 있다.

# "코너는 변호사다." 같이 명제를 나타내는 기호

# "코너는 변호사가 임은 사실이 아니다."를 나타내는 같이, 뒤에 wff가 붙는 부정 기호

# "코너는 변호사이고, 메리는 음악을 좋아한다"를 나타내는 와 같이, 두 개의 wff 사이에 들어오는 네가지 이진 접속사 부정, 곱, 합, 귀결

이런 재귀적 정의는 특정한 기호열이 "좋은 형식"인지 아닌지를 판단하는데 사용할 수 있다는게 가치가 있다.

  • 곱() 양 옆에 원자 wff 가 오므로 는 좋은 형식이다.
  • wff를 바꾸는 부정() 뒤에 wff인 가 오므로 는 좋은 형식이다.
  • 곱() 사이에 모두 wff인 와 가 있으므로 좋은 형식이다.


명제 논리에서 잘 정돈된 공식 (wff)의 개념은 세 가지 규칙을 만족하는 가장 작은 집합으로 재귀적으로 정의된다.

# 는 가 명제 변수이면 wff이다.

# 는 가 wff이면 wff이다.

# 는 와 가 wff이고 •가 논리적 연결자 ∨, ∧, → 또는 ↔ 중 하나이면 wff이다.

이 정의를 사용하여 특정 문자열이 wff인지 여부를 결정할 수 있다.

  • 는 명제 변수 와 가 wff이고 가 논리적 연결자이므로 wff이다.

  • 는 가 wff이므로 wff이다.

  • 는 와 가 wff이고 가 논리적 연결자이므로 wff이다.


논리학이나 컴퓨터 프로그래밍에서 재귀적 정의는 자주 발견된다. 예를 들어, 논리식 (WFF)은 다음과 같이 정의된다.

# 명제를 나타내는 기호 '''p''', '''q''', ...는 WFF이다. (예: '''p'''는 "프레드는 변호사이다", '''q'''는 "메리는 음악을 좋아한다"를 의미)

# '''N'''에 WFF가 부착된 것은 WFF이다. (예: '''N'''이 부정을 나타낸다고 하면, '''Np'''는 "프레드는 변호사이다, 라는 것은 참이 아니다"를 의미)

# 4종류의 논리 연산 ('''C''', '''A''', '''K''', '''E''') 중 하나에, 2개의 WFF가 부착된 것은 WFF이다. (예: '''K'''가 "둘 다 참이다"라는 것을 의미한다고 하면, '''Kpq'''는 "프레드가 변호사이고, 메리는 음악을 좋아한다"는 의미)

# 이상에 의해 WFF로 정의되는 것만이 WFF이다.

이러한 재귀적 정의를 사용하여, 어떤 기호열이 논리식인지 여부를 판정할 수 있다.

  • '''Kpq'''는, WFF인 '''p'''와 '''q'''가 '''K'''에 부착된 것이므로, WFF이다.
  • '''NKpq'''는, WFF인 '''Kpq'''가 '''N'''에 부착된 것이므로, WFF이다.
  • '''KNpNq'''는, '''K'''에 '''Np'''와 '''Nq'''가 부착되어 있고, '''Np''' 및 '''Nq'''는 WFF이므로, WFF이다.
  • '''Npq'''는 WFF가 아니다.

4. 논리 프로그래밍에서의 재귀적 정의

논리 프로그래밍은 재귀적 정의 집합으로 이해될 수 있다.[5][6] 예를 들어, 짝수의 재귀적 정의는 다음과 같은 논리 프로그램으로 작성할 수 있다.

```prolog

even(0).

even(s(s(X))) :- even(X).

```

여기서 `:-`는 'if'를 나타내고, `s(X)`는 `X`의 후계자, 즉 페아노 산술에서와 같이 `X+1`을 나타낸다.

프롤로그는 논리 프로그래밍 언어로서 목표를 해결하고 쿼리에 답하기 위해 후진 추론을 사용한다. 예를 들어, 쿼리 `?- even(s(s(0)))`가 주어지면 `true`라는 답을 생성한다. 쿼리 `?- even(s(0))`가 주어지면 `false`라는 답을 생성한다.

이 프로그램은 쿼리가 참인지 확인하는 데 사용할 수 있을 뿐만 아니라 참인 답을 생성하는 데에도 사용할 수 있다. 예를 들면 다음과 같다.

```prolog

?- even(X).

X = 0

X = s(s(0))

X = s(s(s(s(0))))

X = s(s(s(s(s(s(0))))))

.....

```

논리 프로그램은 실패에 의한 부정을 사용하여 구현된 부정 조건을 포함하여 재귀적 정의를 크게 확장한다. 이는 다음과 같은 정의에서 볼 수 있다.

```prolog

even(0).

even(s(X)) :- not(even(X)).

참조

[1] 논문 On Mathematical Induction 1960
[2] 웹사이트 All About Recursion https://www.cis.upen[...] 2019-10-24
[3] 기타 On Mathematical Induction https://www.jstor.or[...] 1960
[4] 서적 Topology, a first course https://archive.org/[...] Prentice-Hall 1975
[5] 간행물 A logic of nonmonotone inductive definitions. ACM Trans. Comput. Log. 9(2), 14:1–14:52 (2008)
[6] 간행물 A better logical semantics for prolog Springer Nature Switzerland 2023
[7] 서적 An Introduction to Inductive Definitions https://linkinghub.e[...] Elsevier 1977
[8] 저널 On Mathematical Induction 1960
[9] 서적 An Introduction to Inductive Definitions https://linkinghub.e[...] Elsevier 1977
[10] 문서 물론 점화식의 점화(漸化)는 그 점화(点火)가 아니다.
[11] 웹인용 All About Recursion https://www.cis.upen[...] 2019-10-24
[12] 기타 On Mathematical Induction https://www.jstor.or[...] 1960
[13] 서적 Topology, a first course https://archive.org/[...] Prentice-Hall 1975


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com