재귀

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '재귀'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2012년 6월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

Droste 효과로 알려진 재귀의 시각적 형태입니다.이 이미지 속의 여성은 동일한 물체를 들고 있는 자신의 작은 이미지를 담고 있는 물체를 들고 있다.그것은 차례로 동일한 물체를 들고 있는 자신의 작은 이미지 등을 포함하고 있다.1004년 얀 무셋에 의해 디자인된 드로스테 코코아 주석

재귀(적극적: 재귀적)는 어떤 사물이 그 자체 또는 그 유형으로 정의될 때 발생합니다.재귀는 언어학에서 논리학까지 다양한 분야에서 사용된다.재귀의 가장 일반적인 적용은 수학과 컴퓨터 과학에서 정의되는 함수가 자체 정의 내에서 적용되는 것입니다.이는 명백히 무한한 수의 인스턴스(함수 값)를 정의하지만, 대부분의 경우 무한 루프 또는 무한 참조 체인('크록 재귀')이 발생하지 않는 방식으로 수행됩니다.

정식 정의

뱀이나 용이 자신의 꼬리를 먹는 모습을 묘사한 고대 상징인 우로보로스.

수학과 컴퓨터 과학에서 객체 또는 메서드의 클래스는 다음 두 가지 속성으로 정의할 수 있는 경우 재귀적 동작을 나타냅니다.

• 단순한 베이스 케이스(또는 케이스) - 재귀를 사용하여 답변을 생성하지 않는 종료 시나리오
• 재귀 단계 - 기본 케이스로 이어지는 모든 케이스를 줄이는 규칙 집합입니다.

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

• 부모(베이스 케이스) 또는
• 부모의 조상(재귀 단계)

피보나치 시퀀스는 재귀의 또 다른 전형적인 예입니다.

기본 케이스 1로서 섬유(0) = 0,

Fib(1) = 1을 베이스 케이스 2로 한다.

모든 정수 n > 1에 대해 Fib(n) = Fib(n - 1) + Fib(n - 2)입니다.

많은 수학적 공리는 재귀적 규칙에 기초한다.예를 들어, 페아노 공리에 의한 자연수의 공식 정의는 "0은 자연수이고, 각 자연수는 ^[1]자연수인 후계자를 가지고 있다"라고 묘사될 수 있다.이 기본 케이스와 재귀 규칙에 의해 모든 자연수의 집합을 생성할 수 있다.

재귀적으로 정의된 다른 수학적 개체에는 요인, 함수(예: 반복 관계), 집합(예: 칸토어 삼원 집합) 및 프랙탈이 포함된다.

재귀에는 다양한 혀에 의한 정의가 있습니다.재귀 유머를 참조해 주세요.

비공식 정의

최근에 새로워진 사워도, 발효 과정을 거품이 일면서: 레시피는 같은 레시피가 만들어졌을 때 남겨진 사워도 필요합니다.

재귀란 절차 중 하나가 절차 자체를 호출할 때 절차가 통과하는 프로세스입니다.재귀적인 절차를 '재귀적'^[2]이라고 합니다.

재귀를 이해하기 위해서는 프로시저와 프로시저의 실행의 차이를 인식할 필요가 있습니다.프로시저는 일련의 규칙에 근거한 일련의 스텝입니다만, 프로시저의 실행에는 실제로 룰을 따르고 스텝을 실행하는 것이 포함됩니다.

재귀는 다른 프로시저의 실행에 대한 프로시저 사양 내의 참조와 관련되지만 동일하지는 않습니다.

프로시저가 그렇게 정의되면 즉시 무한 루프 가능성이 생깁니다.재귀는 특정 상황에서 절차를 건너뛰어 절차를 완료할 수 있는 경우에만 정의에서 적절하게 사용할 수 있습니다.재귀는 직접, 간접, 순환의 세 가지 형태로 이루어집니다.직접재귀는 함수(A)가 자신을 호출하는 경우(A가 참조하는 경우)이며, 체인 내의 함수 중 하나가 먼저 호출할 때까지 하나의 함수(A)가 호출하는 경우(B), 함수(B)가 호출하는 경우(C), 함수(C)가 호출하는 경우(D), 간접재귀가 발생합니다.순환 재귀는 함수(A)와 함수(B)가 서로 호출할 때 발생합니다.무한 루프가 직접적, 간접적 또는 원형 재귀에서 발생하는 경우, "크록 재귀" 상태라고 합니다.크록 재귀 방지에는 기본적으로 두 가지 방법이 있습니다.즉, 함수가 자신을 참조할 수 있는 횟수를 제한하거나 함수 호출의 깊이에 절대 제한을 두는 것입니다.예를 들어, 깊이 제한이 50인 경우 프로시저가 다른 프로시저를 호출할 때마다 카운터가 증가합니다.프로시저가 종료하면 카운터가 감소합니다.카운터가 제한치(이 경우는 50)에 도달하면, 그 이상의 프로시저 콜은 허가되지 않습니다.51번째 함수를 호출하려고 하면 동작이 종료됩니다.재귀 제한을 사용하면 크락 재귀만 방지됩니다.콜 제한을 설정하면 크락 재귀가 정지되는 것 외에 재귀적이지 않고 깊이 중첩된 정규 복잡한 프로시저가 실행되지 않는 부작용이 발생할 수 있습니다.

그러나 적절하게 정의되어 있다고 해도, 재귀적 절차는 인간이 실행하는 것이 쉽지 않습니다.이는 새로운 절차와 부분적으로 실행된 절차의 호출을 구별할 필요가 있기 때문입니다.이는 절차의 다양한 동시 인스턴스가 얼마나 진행되었는지에 대한 관리를 필요로 합니다.이러한 이유로 재귀적 정의는 일상적인 상황에서 매우 드물다.

언어

언어학자 노암 촘스키는 언어에서 문법적인 문장의 수에 대한 상한이 부족하고 문법적인 문장의 길이에 대한 상한이 없는 것은 자연어에서의 ^[3][4]재귀의 결과로 설명될 수 있다고 주장했다.

이것은 문장과 같은 구문 범주의 재귀적 정의로 이해될 수 있다.문장은 동사 뒤에 오는 것이 다른 문장인 구조를 가질 수 있다.도로시는 마녀들이 위험하다고 생각한다. 마녀들은 위험하다는 문장이 더 큰 문장에서 나온다.그래서 문장은 명사구, 동사, 그리고 선택적으로 다른 문장을 포함하는 구조를 가진 것으로 재귀적으로 정의될 수 있다.이것은 재귀의 수학적 정의의 특별한 경우에 불과합니다.

이것은 언어의 창의성(문법의 무한한 수)을 이해하는 방법을 제공합니다.왜냐하면 문장이 임의의 길이일 수 있다는 것을 즉시 예측하기 때문입니다.도로시는 Toto가 Tin Man이 그렇게 말한 것을 의심하고 있다고 생각합니다.재귀적으로 정의될 수 있는 문장과는 별도로 많은 구조가 있으며, 따라서 문장이 다른 범주의 예를 다른 ^[5]범주의 안에 포함시킬 수 있는 많은 방법이 있다.오랜 세월 동안, 언어들은 일반적으로 이런 종류의 분석에 순응하는 것으로 판명되었다.

하지만, 최근, 재귀가 인간 언어의 필수적인 특성이라는 통념은 피라항어에 대한 그의 주장에 근거해 다니엘 에버렛에 의해 도전을 받아왔다.Andrew Nevins, David Pesetsky, 그리고 Cilene Rodrigues는 ^[6]이것에 반대하는 많은 사람들 중 하나이다.문학적 자기 참조는 어떤 경우에도 수학적 또는 논리적 ^[7]재귀와는 다른 종류의 것으로 주장될 수 있다.

재귀는 구문뿐만 아니라 자연어 의미론에서도 중요한 역할을 합니다.단어와 예를 들어, 문장의 의미에 적용해서 새로운 문장을 만들고 명사구 의미, 동사구 의미 등에 적용할 수 있는 함수로 해석할 수 있다.이것은 또한 자동사, 타동사 또는 타동사에도 적용될 수 있다.적절하게 유연하고 일반적으로 이러한 다른 유형의 의미를 인수로서 받아들일 수 있도록 정의된 단일 표현을 제공하기 위해.이것은 문장을 조합하는 단순한 경우를 정의하고, 다른 경우를 단순한 ^[8]경우를 재귀적으로 정의함으로써 이루어질 수 있다.

재귀 문법은 재귀 생성 ^[9]규칙을 포함하는 형식 문법입니다.

재귀적 유머

재귀적 위키백과 페이지

재귀는 컴퓨터 과학, 프로그래밍, 철학 또는 수학 교과서에서 일반적으로 순환 정의 또는 자기 참조를 제공함으로써 유머러스하게 사용됩니다. 여기서 추정 재귀 단계는 기본 케이스에 더 가까이 가지 않고 대신 무한 퇴행으로 이어집니다.이러한 책들이 용어집에 다음과 같은 우스갯소리를 포함하는 것은 드문 일이 아니다.

재귀.^[10] 재귀 참조.

Brian Kernighan과 Dennis Ritchie의 책 The C Programming Language의 일부 판 색인에서 변화가 발견됩니다. 색인 항목은 반복적으로 자신을 참조합니다("재귀 86, 139, 141, 182, 202, 269").이 농담의 초기 버전은 Laurent Siklossy의 Laurent's talk Lisp(1975년 12월 1일 출판, 저작권 날짜 1976년)와 Kernighan and Plauger의 소프트웨어 도구(1976년 1월 11일 애디슨-Wesley Professional에 의해 출판됨)에서 찾을 수 있습니다.이 농담은 Kernighan과 Pike의 UNIX Programming Environment에서도 볼 수 있습니다.그것은 The C Programming Language 초판에는 실리지 않았다.이 농담은 기능 프로그래밍 민속의 일부이며 앞서 언급한 책들이 출판되기 전에 기능 프로그래밍 커뮤니티에 이미 널리 퍼져 있었다.

또 다른 농담은 "재귀를 이해하기 위해서는 ^[10]재귀를 이해해야 한다"는 것이다.영문판 구글 웹 검색 엔진에서 "재귀"를 검색하면 "재귀"^[11]를 의미합니까?Andrew Plotkin의 다른 형식은 다음과 같습니다. "재귀가 무엇인지 이미 알고 있다면 답을 기억하십시오. 그렇지 않으면 당신보다 더글라스 호프스타터 근처에 서 있는 사람을 찾아서 재귀가 무엇인지 물어보세요."

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

수학에서

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

재귀적으로 정의된 집합

예: 자연수

재귀적으로 정의된 집합의 표준 예는 자연수로 나타납니다.

0은 N$(\$에 있습니다.

n이 N$(\$이면 n + 1은 N$(\$입니다$.$

자연수의 집합은 앞의 두 특성을 만족시키는 가장 작은 집합입니다.

수학 논리학에서, 페아노 공리(또는 페아노 공식 또는 데데킨트-페아노 공리)는 독일의 수학자 리처드 데데킨트와 이탈리아 수학자 주세페 페아노가 19세기에 제시한 자연수에 대한 공리이다.Peano Axioms는 자연수를 재귀적 함수로서 정의하고 덧셈과 곱셈을 재귀적 함수로 정의합니다.

예: 증명 절차

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

• 만약 명제가 공리라면, 그것은 입증 가능한 명제이다.
• 만약 어떤 명제가 추론 규칙을 통해 진정한 도달 가능한 명제로부터 도출될 수 있다면, 그것은 입증 가능한 명제이다.
• 증명 가능한 명제 집합은 이러한 조건을 만족시키는 가장 작은 명제 집합이다.

유한분할규칙

유한 분할 규칙은 재귀의 기하학적 형태로 프랙탈과 같은 이미지를 만드는 데 사용할 수 있습니다.하위 분할 규칙은 여러 개의 레이블로 레이블이 지정된 폴리곤 집합에서 시작하여 각 폴리곤이 원래 폴리곤의 레이블에만 의존하는 방식으로 더 작은 레이블이 지정된 폴리곤으로 세분됩니다.이 프로세스를 반복할 수 있습니다.칸토어 집합을 만들기 위한 표준 'middleth' 기술은 중심 분할과 마찬가지로 분할 규칙입니다.

기능 재귀

함수는 그 자체로 재귀적으로 정의될 수 있다.일반적인 예는 F(n) = F(n - 1) + F(n - 2)의 피보나치 수열입니다.이러한 정의가 유용하기 위해서는 이 경우 F(0) = 0 및 F(1) = 1과 같이 비연속적으로 정의된 값으로 환원할 수 있어야 한다.

유명한 재귀 함수는 피보나치 수열과 달리 재귀 ^{[citation needed]}없이 표현될 수 없는 Ackermann 함수입니다.

재귀적 정의를 수반하는 증명

이전 절에서와 같이 반복적으로 정의된 집합이나 함수에 케이스에 의한 표준 증명 기술을 적용하면 구조 귀납을 얻을 수 있습니다.구조 귀납은 수리 논리 및 컴퓨터 과학에서 증명을 도출하기 위해 널리 사용되는 수학적 귀납의 강력한 일반화입니다.

재귀 최적화

동적 프로그래밍은 다주기 또는 다단계 최적화 문제를 재귀 형식으로 재작성하는 최적화에 대한 접근법입니다.동적 프로그래밍의 주요 결과는 벨만 방정식입니다. 벨만 방정식은 최적화 문제의 값을 더 빠른 시간(또는 더 빠른 단계)에 씁니다.

재귀 정리

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

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

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

모든 자연수 n에 대해

고유성 증명

다음과 같은 두 가지 $함수{\displaystyle }$F:${\displaystyle N\mathbb{}}$ ${\displaystyle \to }$ {\$displaystyle$ F$:\mathbb {N}$ \$to$X} $및$ G${\displaystyle :N\mathbb{}}$ ${\displaystyle \to }$ {\$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에 대해 유지됩니다.

유도 단계: 일부 $k{\displaystyle n\mathbb{}}$N {\$displaystyle$ k$\in \mathbb {N$에 대해 F(k) = G(k)라고 가정하면 F(k + 1) = f(F(k) = G(k + 1)입니다.

따라서 F(k) = G(k)는 F(k + 1) = G(k + 1)를 의미합니다.

유도에 의해 $모든{\displaystyle }$ n${\displaystyle n\mathbb{}}$N {\$displaystyle$ n$\in \mathbb {N$에 대해 F(n) = G(n)이다.

컴퓨터 공학에서

일반적인 단순화 방법은 문제를 같은 유형의 하위 문제로 나누는 것입니다.컴퓨터 프로그래밍 기술로서 이것은 분할과 정복이라고 불리며 많은 중요한 알고리즘의 설계에 핵심이다.분할 및 정복은 문제 해결에 대한 하향식 접근 방식으로서, 점점 더 작은 인스턴스를 해결함으로써 문제를 해결합니다.반대되는 접근법은 동적 프로그래밍입니다.이 접근방식은 원하는 규모에 도달할 때까지 점점 더 큰 인스턴스를 해결함으로써 문제를 해결하는 상향식 접근법 역할을 합니다.

재귀의 전형적인 예로는 C 코드로 제공되는 요인 함수의 정의가 있습니다.

서명되어 있지 않다 인트 요인(서명되어 있지 않다 인트 n) {     한다면 (n == 0) {         돌아가다 1;     } 또 다른 {         돌아가다 n * 요인(n - 1);     } } 

함수는 작은 버전의 입력에서 반복적으로 호출됩니다.(n - 1)재귀 콜의 결과를 곱합니다.n기본 케이스에 도달할 때까지, 요인의 수학적 정의와 유사하게.

컴퓨터 프로그래밍의 재귀는 함수가 더 단순하고 종종 더 작은 버전의 함수로 정의될 때 예시됩니다.그런 다음 문제의 단순한 버전에서 얻은 해결책을 조합하여 문제의 해결책을 고안합니다.재귀 적용의 한 예는 프로그래밍 언어를 위한 파서입니다.재귀의 큰 장점은 무한한 일련의 가능한 문장, 디자인 또는 다른 데이터를 유한한 컴퓨터 프로그램에 의해 정의, 해석 또는 생성할 수 있다는 것입니다.

반복 관계는 하나 이상의 시퀀스를 재귀적으로 정의하는 방정식입니다.일부 특정 종류의 반복 관계를 "해결"하여 비재귀적 정의(예: 닫힌 형식 식)를 얻을 수 있습니다.

알고리즘에서 재귀 사용에는 장점과 단점이 있습니다.주된 장점은 보통 명령의 단순성입니다.주요 단점은 재귀 알고리즘의 메모리 사용량이 매우 빠르게 증가하여 더 큰 인스턴스에서 실행 불가능할 수 있다는 것입니다.

생물학에서

재귀적 과정에 의해 만들어진 것으로 보이는 모양은 하나의 큰 부분이 두 개 이상의 유사한 작은 부분으로 갈라지는 가지 구조에서와 같이 식물과 동물에서 가끔 나타납니다.로마네스코 ^[12]브로콜리가 그 예입니다.

인 아트

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

1320년 지오토의 스테파네치 트리프티치의 정면에는 반복적으로 자신의 이미지가 들어있다.

러시아 인형이나 마트료쉬카 인형은 재귀적 ^[13]개념의 물리적 예술적 예시이다.

재귀는 1320년에 만들어진 지오토의 스테파네치 트리프티치 이후 그림에 사용되어 왔다.중앙 패널에는 무릎을 꿇고 있는 스테파네치 추기경의 형상이 들어 있으며, 세 개의 그림 자체를 ^[14][15]제물로 들고 있다.이 방법은 일반적으로 Droste 효과로 알려져 있으며, Mise en abyme 기법의 한 예입니다.

M. C. 에셔의 프린트 갤러리(1956)는 그림이 반복적으로 담긴 갤러리를 포함한 왜곡된 도시를 그린 인쇄물이며, 그래서 무한하다.^[16]

「 」를 참조해 주세요.

레퍼런스

참고 문헌

외부 링크

Wikimedia Commons에는 재귀 유머와 관련된 미디어가 있습니다.

무료 사전인 Wiktionary에서 재귀 또는 재귀성을 검색합니다.

• 재귀 - Alan Gauld의 튜토리얼
• ZIP 파일 완전 다운
• 네빈스, 앤드류, 데이비드 페세츠키, 실린 로드리게스.증거와 주장: 에버렛에 대한 답변(2009).언어 85.3: 671-681 (2009)