재귀

컴퓨터 과학 용어에 대해서는 재귀 (컴퓨터 과학) 문서를 참고하십시오.

재귀(recursion)는 개념이나 과정의 정의가 그것 자체의 더 간단하거나 이전 버전에 의존할 때 발생한다.^[1] 재귀는 언어학에서 논리학에 이르는 다양한 분야에서 사용된다. 재귀의 가장 일반적인 응용은 수학과 컴퓨터 과학에서 정의되는 함수가 자체 정의 내에서 적용될 때이다. 이는 겉보기에는 무한한 수의 인스턴스(함수 값)를 정의하지만, 무한 루프나 무한한 참조 체인이 발생하지 않도록 종종 수행된다.

드로스테 효과로 알려진 재귀의 시각적 형태. 이 이미지의 여성은 자신과 동일한 물건을 들고 있는 자신의 작은 이미지를 포함하는 물건을 들고 있으며, 이는 다시 자신과 동일한 물건을 들고 있는 자신의 작은 이미지를 포함하는 식이다. 얀 미셋이 디자인한 1904년 드로스테 코코아 통.

재귀를 나타내는 과정은 재귀적이다. 비디오 피드백은 재귀적 이미지를 표시하며, 인피니티 미러도 마찬가지이다.

형식적 정의

자신의 꼬리를 먹는 뱀 또는 용을 묘사하는 고대 상징인 우로보로스

수학과 컴퓨터 과학에서 객체 또는 방법의 클래스는 다음 두 가지 속성으로 정의될 수 있을 때 재귀적 동작을 나타낸다.

• 단순한 기본 사례(또는 사례) — 답을 생성하기 위해 재귀를 사용하지 않는 종료 시나리오
• 재귀 단계 — 모든 연속적인 사례를 기본 사례로 축소하는 규칙 집합.

예를 들어, 다음은 사람의 조상에 대한 재귀적 정의이다. 한 사람의 조상은 다음 중 하나이다.

• 자신의 부모 (기본 사례), 또는
• 자신의 부모의 조상 (재귀 단계).

피보나치 수열은 재귀의 또 다른 고전적인 예이다.

Fib(0) = 0을 기본 사례 1로,

Fib(1) = 1을 기본 사례 2로,

모든 정수 n > 1에 대해, Fib(n) = Fib(n − 1) + Fib(n − 2).

많은 수학적 공리는 재귀적 규칙을 기반으로 한다. 예를 들어, 페아노 공리계에 의한 자연수의 형식적 정의는 "0은 자연수이며, 각 자연수는 계승자를 가지며, 이는 또한 자연수이다"라고 설명될 수 있다.^[2] 이 기본 사례와 재귀 규칙을 통해 모든 자연수 집합을 생성할 수 있다.

다른 재귀적으로 정의된 수학적 객체로는 계승, 함수 (예: 점화식), 집합 (예: 칸토어 집합), 프랙탈 등이 있다.

재귀에 대한 다양한 유머러스한 정의가 있다. 재귀적 유머를 참조하라.

비형식적 정의

사워도 스타터를 밀가루에 섞어 사워도우를 만드는 모습: 레시피에는 지난번에 같은 레시피를 만들고 남은 사워도우가 필요하다.

재귀는 절차의 단계 중 하나가 절차 자체를 호출하는 것을 포함할 때 절차가 거치는 과정이다. 재귀를 거치는 절차는 '재귀적'이라고 한다.^[3]

재귀를 이해하려면 절차와 절차의 실행 사이의 구별을 인식해야 한다. 절차는 일련의 규칙을 기반으로 한 단계 집합이며, 절차의 실행은 실제로 규칙을 따르고 단계를 수행하는 것을 포함한다.

재귀는 절차의 사양 내에서 다른 절차의 실행에 대한 참조와 관련이 있지만 동일하지는 않다.

절차가 이렇게 정의될 때, 이는 즉시 끝없는 루프의 가능성을 생성한다. 재귀는 해당 단계가 특정 경우에 건너뛰어져 절차가 완료될 수 있도록 정의에서만 올바르게 사용될 수 있다.

제대로 정의되었더라도 재귀적 절차는 인간이 수행하기 쉽지 않다. 왜냐하면 절차의 새롭고 부분적으로 실행된 호출을 구별해야 하기 때문이다. 이는 절차의 다양한 동시 인스턴스가 얼마나 진행되었는지에 대한 일부 관리가 필요하다. 이러한 이유로 재귀적 정의는 일상생활에서 매우 드물다.

언어에서

언어학자 노엄 촘스키는 다른 많은 사람들과 함께 언어의 문법적인 문장 수에 대한 상한선이 없다는 점과 문법적인 문장 길이(발화에 사용 가능한 시간과 같은 실제적인 제약 외에)에 대한 상한선이 없다는 점이 자연어의 재귀의 결과로 설명될 수 있다고 주장했다.^[4][5]

이는 문장과 같은 통사 범주의 재귀적 정의로 이해될 수 있다. 문장은 동사 뒤에 다른 문장이 오는 구조를 가질 수 있다. '도로시는 마녀들이 위험하다고 생각한다'에서 '마녀들이 위험하다'는 문장이 더 큰 문장 안에 포함되어 있다. 따라서 문장은 (대략적으로) 명사구, 동사, 그리고 선택적으로 다른 문장을 포함하는 구조를 가진 것으로 재귀적으로 정의될 수 있다. 이것은 실제로는 재귀의 수학적 정의의 특별한 경우에 불과하다.

이는 언어의 창조성, 즉 무한한 수의 문법적인 문장을 이해하는 방법을 제공한다. 왜냐하면 문장이 임의의 길이를 가질 수 있음을 즉시 예측하기 때문이다. "도로시는 토토가 양철 인간이 말한 것을 의심한다고 생각한다..." 문장 외에도 재귀적으로 정의될 수 있는 많은 구조가 있으며, 따라서 문장이 한 범주의 인스턴스를 다른 범주 안에 포함시킬 수 있는 많은 방법이 있다.^[6] 수년에 걸쳐 언어는 일반적으로 이러한 종류의 분석에 적합함이 입증되었다.

재귀가 인간 언어의 본질적인 속성이라는 일반적으로 받아들여지는 생각은 대니얼 에버렛이 피라항어에 대한 자신의 주장을 바탕으로 이의를 제기했다. 앤드루 네빈스, 데이비드 페세츠키, 실레네 로드리게스는 이에 반대하는 많은 사람들 중 일부이다.^[7] 문학적 자기언급은 어떤 경우든 수학적 또는 논리적 재귀와는 종류가 다르다고 주장될 수 있다.^[8]

재귀는 구문뿐만 아니라 자연어 의미론에서도 중요한 역할을 한다. 예를 들어 'and'라는 단어는 문장 의미에 적용되어 새로운 문장을 생성하는 함수로 해석될 수 있으며, 명사구 의미, 동사구 의미 등도 마찬가지이다. 이는 또한 자동사, 타동사 또는 이중타동사에도 적용될 수 있다. 유연하게 적절한 단일 의미를 제공하기 위해 'and'는 일반적으로 이러한 다양한 유형의 의미를 인수로 취할 수 있도록 정의된다. 이는 문장을 결합하는 간단한 경우에 대해 정의한 다음, 간단한 경우를 재귀적으로 사용하여 다른 경우를 정의함으로써 수행할 수 있다.^[9]

재귀 문법은 재귀적인 생성 규칙을 포함하는 형식 문법이다.^[10]

재귀적 유머

재귀는 때때로 컴퓨터 과학, 프로그래밍, 철학 또는 수학 교과서에서 유머러스하게 사용되는데, 일반적으로 순환 정의 또는 자기언급을 통해 이루어지며, 이때 추정되는 재귀적 단계는 기본 사례에 가까워지지 않고 오히려 무한 후퇴로 이어진다. 그러한 책들이 다음 줄의 용어집에 농담 항목을 포함하는 것은 드문 일이 아니다.

재귀, 재귀를 참조하라.^[11]

변형은 브라이언 커니핸과 데니스 리치의 책 The C Programming Language의 일부 판본의 색인 269페이지에서 찾을 수 있다. 색인 항목은 자신을 재귀적으로 참조한다("recursion 86, 139, 141, 182, 202, 269"). 이 농담의 초기 버전은 로랑 시클로시(Laurent Siklóssy)의 'Let's talk Lisp'(Prentice Hall PTR, 1975년 12월 1일 발행, 1976년 저작권)과 커니핸과 플라우거(Plauger)의 'Software Tools'(Addison-Wesley Professional, 1976년 1월 11일 발행)에서 찾아볼 수 있다. 이 농담은 커니핸과 파이크(Pike)의 'The UNIX Programming Environment'에도 나온다. 'The C Programming Language'의 초판에는 나타나지 않았다. 이 농담은 함수형 프로그래밍 민속의 일부이며, 앞서 언급된 책들이 출판되기 전부터 함수형 프로그래밍 커뮤니티에 널리 퍼져 있었다.^[12][13]

토론토 재귀 역사 프로젝트의 토론토 재귀 역사를 기념하는 명판.

또 다른 농담은 "재귀를 이해하려면 재귀를 이해해야 한다"이다.^[11] 구글 웹 검색 엔진의 영어 버전에서 "recursion"을 검색하면, "Did you mean: recursion."이라고 제안한다.^[14] 더글러스 호프스태터가 제시한 또 다른 형태는 다음과 같다: "이미 재귀가 무엇인지 알고 있다면, 그 답을 기억하기만 하라. 그렇지 않다면, 당신보다 더글러스 호프스태터에게 더 가까이 서 있는 사람을 찾아 그에게 재귀가 무엇인지 물어보라."

재귀 약자는 재귀적 유머의 또 다른 예이다. 예를 들어, PHP는 "PHP Hypertext Preprocessor"의 약자이고, WINE은 "WINE Is Not an Emulator"의 약자이며, GNU는 "GNU's not Unix"의 약자이고, SPARQL은 "SPARQL Protocol and RDF Query Language"를 나타낸다.

수학에서

시에르핀스키 삼각형 — 프랙탈을 형성하는 삼각형의 제한된 재귀

재귀적으로 정의된 집합

 이 부분의 본문은 재귀적 정의입니다.

예시: 자연수

 폐포 (수학) 문서를 참고하십시오.

재귀적으로 정의된 집합의 정식적인 예는 자연수에 의해 주어진다.

0은 ${\displaystyle \mathbb {N} }$에 속한다

n이 ${\displaystyle \mathbb {N} }$에 속한다면, n + 1도 ${\displaystyle \mathbb {N} }$에 속한다

자연수의 집합은 앞의 두 속성을 만족하는 가장 작은 집합이다.

수리논리학에서 페아노 공리계 (또는 페아노 공준 또는 데데킨트-페아노 공리계)는 19세기 독일 수학자 리하르트 데데킨트와 이탈리아 수학자 주세페 페아노가 제시한 자연수에 대한 공리이다. 페아노 공리계는 재귀적 계승 함수와 덧셈 및 곱셈을 재귀 함수로 참조하여 자연수를 정의한다.

예시: 증명 절차

또 다른 흥미로운 예는 다음과 같이 귀납적(또는 재귀적)으로 정의된 증명 절차의 관점에서 정의되는 공리계의 모든 "증명 가능한" 명제 집합이다.

• 명제가 공리이면 증명 가능한 명제이다.
• 명제가 추론 규칙을 통해 참인 도달 가능한 명제로부터 도출될 수 있다면 증명 가능한 명제이다.
• 증명 가능한 명제의 집합은 이 조건을 만족하는 가장 작은 명제 집합이다.

유한 세분 규칙

 이 부분의 본문은 유한 세분 규칙입니다.

유한 세분 규칙은 재귀의 기하학적 형태로, 프랙탈과 같은 이미지를 생성하는 데 사용될 수 있다. 세분 규칙은 유한한 수의 레이블로 레이블링된 다각형 집합으로 시작하며, 각 다각형은 원래 다각형의 레이블에만 의존하는 방식으로 더 작은 레이블링된 다각형으로 세분된다. 이 과정은 반복될 수 있다. 칸토어 집합을 생성하는 표준 '중앙 3분의 1' 기술은 세분 규칙이며, 중심 세분도 마찬가지이다.

함수적 재귀

함수는 자신을 사용하여 재귀적으로 정의될 수 있다. 친숙한 예는 피보나치 수열: F(n) = F(n − 1) + F(n − 2)이다. 이러한 정의가 유용하려면 비재귀적으로 정의된 값으로 환원될 수 있어야 한다. 이 경우 F(0) = 0 및 F(1) = 1이다.

재귀적 정의를 포함하는 증명

재귀적으로 정의된 집합이나 함수에 경우의 수에 의한 증명의 표준 기술을 적용하면, 이전 섹션에서와 같이 구조적 귀납법이 나온다. 이는 수학적 귀납법의 강력한 일반화로, 수리논리학과 컴퓨터 과학에서 증명을 도출하는 데 널리 사용된다.

재귀적 최적화

동적 계획법은 다기간 또는 다단계 최적화 문제를 재귀적 형태로 재정의하는 최적화 접근 방식이다. 동적 계획법의 핵심 결과는 벨만 방정식으로, 이전 시간(또는 이전 단계)의 최적화 문제 값을 나중 시간(또는 나중 단계)의 값으로 표현한다.

재귀 정리

집합론에서 이것은 재귀적으로 정의된 함수가 존재함을 보장하는 정리이다. 집합 X, X의 원소 a, 그리고 함수 f: X → X가 주어졌을 때, 이 정리는 다음을 만족하는 유일한 함수 ${\displaystyle F:\mathbb {N} \to X}$ (여기서 ${\displaystyle \mathbb {N} }$은 0을 포함하는 자연수 집합을 나타낸다)가 존재함을 명시한다.

${\displaystyle F(0)=a}$

${\displaystyle F(n+1)=f(F(n))}$

모든 자연수 n에 대해.

데데킨트는 ${\displaystyle \mathbb {N} }$에 대한 집합론적 함수의 고유한 재귀적 정의 문제를 처음 제기했으며, 1888년 에세이 "Was sind und was sollen die Zahlen?"에서 주장의 개요를 제시했다.^[15]

유일성 증명

다음과 같은 두 함수 ${\displaystyle F:\mathbb {N} \to X}$와 ${\displaystyle G:\mathbb {N} \to X}$를 가정한다.

${\displaystyle F(0)=a}$

${\displaystyle G(0)=a}$

${\displaystyle F(n+1)=f(F(n))}$

${\displaystyle G(n+1)=f(G(n))}$

여기서 a는 X의 원소이다.

모든 자연수 n에 대해 F(n) = G(n)임을 수학적 귀납법으로 증명할 수 있다.

기본 사례: F(0) = a = G(0)이므로, n = 0에 대해 등식이 성립한다.

귀납적 단계: 어떤 ${\displaystyle k\in \mathbb {N} }$에 대해 F(k) = G(k)라고 가정하자. 그러면 F(k + 1) = f(F(k)) = f(G(k)) = G(k + 1)이 된다.

따라서 F(k) = G(k)는 F(k + 1) = G(k + 1)을 의미한다.

귀납법에 의해, 모든 ${\displaystyle n\in \mathbb {N} }$에 대해 F(n) = G(n)이 성립한다.

컴퓨터 과학에서

 이 부분의 본문은 재귀 (컴퓨터 과학)입니다.

일반적인 단순화 방법은 문제를 동일한 유형의 하위 문제로 나누는 것이다. 컴퓨터 프로그래밍 기술로서 이것은 분할 정복이라고 불리며 많은 중요한 알고리즘 설계의 핵심이다. 분할 정복은 문제를 점점 더 작게 나누어 해결하는 하향식 문제 해결 접근 방식이다. 그 반대 접근 방식은 동적 계획법이다. 이 접근 방식은 문제를 점점 더 크게 해결하여 원하는 크기에 도달할 때까지 해결하는 상향식 접근 방식이다.

재귀의 고전적인 예는 계승 함수를 정의하는 것으로, 파이썬 코드에서는 다음과 같다.

def factorial(n):
    if n > 0:
        return n * factorial(n - 1)
    else:
        return 1

이 함수는 입력 (n - 1)의 더 작은 버전으로 재귀적으로 자신을 호출하고, 재귀 호출의 결과를 n으로 곱하며, 계승의 수학적 정의와 유사하게 기본 사례에 도달할 때까지 반복한다.

컴퓨터 프로그래밍에서 재귀는 함수가 자신보다 더 간단하고 종종 더 작은 버전으로 정의될 때 예시된다. 문제에 대한 해결책은 문제의 더 간단한 버전에서 얻은 해결책을 결합하여 고안된다. 재귀의 한 가지 응용 예는 프로그래밍 언어용 파서이다. 재귀의 큰 장점은 무한한 수의 가능한 문장, 디자인 또는 기타 데이터를 유한한 컴퓨터 프로그램으로 정의, 구문 분석 또는 생성할 수 있다는 것이다.

점화식은 하나 이상의 수열을 재귀적으로 정의하는 방정식이다. 특정 종류의 점화식은 비재귀적 정의(예: 폐쇄형 식)를 얻기 위해 "해결"될 수 있다.

알고리즘에서 재귀를 사용하는 것은 장점과 단점 모두를 가진다. 주요 장점은 일반적으로 명령의 단순성이다. 주요 단점은 재귀 알고리즘의 메모리 사용량이 매우 빠르게 증가하여 더 큰 인스턴스에는 비실용적일 수 있다는 것이다.

생물학에서

재귀적 과정으로 만들어진 것처럼 보이는 형태는 식물과 동물에서 때때로 나타난다. 예를 들어, 하나의 큰 부분이 두 개 이상의 유사한 작은 부분으로 갈라지는 가지 구조가 그러하다. 로마네스코 브로콜리가 그 예이다.^[16]

사회과학에서

저자들은 재귀성 개념을 사용하여 사회 과학자들이 자신이 이미 속한 세계에 대한 지식을 생산할 때 처하는 상황을 강조한다.^[17][18] 오드리 알레한드로에 따르면, "사회 과학자로서 우리의 조건의 재귀성은 우리가 (담론이 우리가 분석하는 매체이므로) 주체이기도 하고, (우리가 분석하는 세계에 속하는 사회적 행위자이므로) 우리가 생산하는 학술 담론의 객체이기도 하다는 사실을 다룬다."^[19] 이 기반에서 그녀는 재귀성에서 해방적 지식 생산의 근본적인 도전을 식별하며, 이는 성찰적 노력을 요구한다.

우리는 우리가 도전하고자 하는 사회정치적 질서에 의해 생산된 담론과 성향으로 사회화되며, 따라서 우리는 정반대의 목표를 가지고 있음에도 불구하고 무의식적으로 이 사회정치적 질서를 재현할 수 있다. 학자로서 우리의 상황의 재귀성 – 그리고 더 정확히 말하면, 우리가 세계에 대한 지식을 생산하는 데 사용하는 성향적 도구 자체가 이 세계에 의해 생산된다는 사실 – 은 실천에서 성찰성을 구현하는 것이 필수적임을 보여줄 뿐만 아니라, 그렇게 하는 데 주요한 도전을 제기한다.

— 오드리 알레한드로, Alejandro (2021)

경영학에서

 경영 사이버네틱스 문서에 이 부분의 추가 정보가 있습니다.

재귀는 때때로 경영학에서 대기업의 추상화 수준을 반복하는 과정으로 언급된다.^[20] 일반적인 예는 중간 관리직을 통해 라인 관리직에서 고위 관리직에 이르는 관리 계층의 재귀적 특성이다. 이는 또한 기업지배구조에서 자본구조라는 더 큰 문제도 포함한다.^[21]

예술에서

재귀 인형: 즈뵤즈도치킨과 말류틴의 오리지널 마트료시카 세트, 1892년

조토 디 본도네의 스테파네스키 삼면화, 1320년, 앞면은 삼면화 자체를 들고 있는 무릎 꿇은 인물(중앙 패널)의 이미지를 재귀적으로 포함한다.

 수학과 예술 및 인피니티 미러 문서를 참고하십시오.

마트료시카는 재귀 개념의 물리적인 예술적 예시이다.^[22]

재귀는 조토 디 본도네의 1320년작 스테파네스키 삼면화 이후 그림에서 사용되었다. 이 작품의 중앙 패널에는 삼면화 자체를 봉헌물로 들고 있는 무릎 꿇은 스테파네스키 추기경의 모습이 담겨 있다.^[23][24] 이 관행은 더 일반적으로 드로스테 효과라고 알려져 있으며, 미장아빔 기법의 한 예이다.

마우리츠 코르넬리스 에셔의 판화 화랑 (1956)은 왜곡된 도시를 묘사하는 판화로, 그 도시는 판화 자체를 재귀적으로 포함하고 있으며, 이는 무한히 반복된다.^[25]

문화에서

영화 인셉션은 명사에 접미사 -ception을 붙여 무언가의 재귀를 농담조로 나타내는 것을 일상화시켰다.^[26]

같이 보기

• 재귀 (컴퓨터 과학)
• 재귀 함수
• 점화식