Jump to content

Recursion

This is a fully translated article. Click here for more information.
From DawoumWiki, the free Mathematics self-learning
A visual form of recursion known as the Droste effect. The woman in this image holds an object that contains a smaller image of her holding an identical object, which in turn contains a smaller image of herself holding an identical object, and so forth. 1904 Droste cocoa tin, designed by Jan Musset

재귀(recursion)는 어떤 것이 그 자체 또는 그의 유형의 관점에서 정의될 때 발생합니다. 재귀는 언어학(linguistics)에서 논리학(logic)에 이르기까지 다양한 분야에서 사용됩니다. 재귀의 가장 일반적인 응용은 수학컴퓨터 과학 안에 있으며, 여기서 정의되는 함수(function)는 그 자체 정의 내에서 적용됩니다. 이것은 분명히 무한한 숫자의 인스턴스 (함수 값)를 정의하는 반면에, 그것은 루프 또는 참조의 무한 체인이 발생할 수 없는 방식으로 종종 수행됩니다.

Formal definitions

Ouroboros, an ancient symbol depicting a serpent or dragon eating its own tail.

수학 그리고 컴퓨터 과학에서, 대상 또는 방법의 클래스는, 그들이 다음 두 속성에 의해 정의될 때, 재귀적 동작을 나타냅니다:

  1. 간단한 기본 경우 (또는 기초)—응답을 생성하기 위해서 재귀를 사용하지 않는 종료 시나리오
  2. 모든 다른 경우를 기본 경우쪽으로 줄이는 규칙의 집합

예를 들어, 다음은 사람의 조상의 재귀적 정의입니다:

  • 한 사람의 부모(parent)는 그 사람의 조상(ancestor)입니다 (기본 경우).
  • 한 사람의 조상의 조상은 역시 그 사람의 조상입니다 (재귀 단계).

피보나치 수열(Fibonacci sequence)은 재귀의 고전적인 예제입니다:

많은 수학적 공리는 재귀적 규칙을 기반으로 합니다. 예를 들어, 페아노 공리(Peano axioms)에 의한 자연수의 공식적인 정의는 다음으로 설명될 수 있습니다: 0은 자연수이고, 각 자연수는 후임을 가지며, 이것 역시 자연수입니다. 이 기본 경우와 재귀적 규칙에 의해, 모든 자연수 집합을 생성할 수 있습니다.

재귀적으로 정의된 수학적 대상은 함수(function), 집합(sets), 그리고 특히 프랙탈(fractal)을 포함합니다.

재귀의 다양한 보다 장난같은 "정의"가 있습니다; 재귀적인 유머(recursive humor)를 참조하십시오.

Informal definition

Recently refreshed sourdough, bubbling through fermentation: the recipe calls for some sourdough left over from the last time the same recipe was made.

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

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

재귀는 어떤 다른 절차의 실행에 대한 절차의 사양 내의 참조와 관련이 있지만 같지는 않습니다.

절차가 이와 같이 정의될 때, 이것은 즉시 무한 루프의 가능성을 생성합니다; 재귀는 만약 질문에서 단계가 절차가 완료될 수 있도록 특정 경우에서 건너뛰면 정의에서 오직 적절하게 사용될 수 있습니다.

그러나 재귀 절차는, 심지어 그것이 적절하게 정의되더라도, 사람에게 수행하기에 쉽지 않은데, 왜냐하면 그것은 부분적으로 실행된 절차의 호출을 이전 것을 새 것과 구분하는 것을 요구하기 때문입니다; 이것은 절차의 다양한 동시 인스턴스가 얼마나 진행되었는지에 대한 어떤 관리를 요구합니다. 이러한 이유로, 재귀 정의는 일상적인 상황에서 매우 드뭅니다.

In language

언어학자 노암 촘스키(Noam Chomsky)는, 다른 사람들 중에서, 언어에서 문법적 문장의 수에 대한 위쪽 경계의 없음과, (말을 할 수 있는 시간과 같은 실질적인 제약을 넘어서) 문법적 문장 길이에 대한 위쪽 경계가 없음은 자연 언어에서 재귀의 결과로 설명될 수 있다고 주장해 왔습니다.[2][3]

이것은 문장과 같은 구문 카테고리의 재귀 정의의 관점에서 이해될 수 있습니다. 문장은 동사 다음에 오는 또 다른 문장이 있는 구조를 가질 수 있습니다: 도로시는 마녀가 위험하다고 생각합니다, 이것에서 문장 마녀가 위험하다는 더 큰 문장에서 발생합니다. 따라서 문장은 명사구, 동사, 및 선택적으로 다른 문장을 포함하는 구조를 가진 어떤 것으로 (매우 대략) 재귀적으로 정의될 수 있습니다. 이것은 단지 재귀의 수학적 정의의 특별한 경우일 뿐입니다.

이것은 문장의 길이가 임의적일 수 있음을 즉시 예측하기 때문에 언어의 창의성–문법적 문장의 무한한 수–을 이해하는 방법을 제공합니다: 도로시는 토토가 틴 맨이 ...이라고 말한 것을 의심한다고 생각합니다. 재귀적으로 정의될 수 있는 문장, 따라서 문장이 한 카테고리의 인스턴스를 또 다른 카테고리 안에 포함할 수 있는 여러 방법이 있는 문장과는 별개로 많은 구조가 있습니다.[4] 수년에 걸쳐, 언어가 일반적으로 이러한 종류의 분석에 적합하다는 것이 입증되었습니다.

최근에, 어쨌든, 재귀가 인간 언어의 필수 속성이라는 일반적으로 받아들여진 아이디어가 다니엘 에버렛(Daniel Everett)에 의해 피라한 언어(Pirahã language)에 대한 자신의 주장을 근거로 이의를 제기해 왔습니다. Andrew Nevins, David Pesetsky, 및 Cilene Rodrigues는 이에 대해 반대하는 많은 사람들 중에 있습니다.[5] 문학적 자기-참조(self-reference)는 어떤 경우에도 수학적 또는 논리적 재귀와 종류가 다르다고 주장할 수 있습니다.[6]

재귀는 구문뿐만 아니라 자연 언어 의미론(natural language semantics)에서도 중요한 역할을 합니다. 단어 and는, 예를 들어, 새로운 문장을 생성하기 위해 문장 의미에 적용할 수 있는 기능으로 해석될 수 있고, 명사구 의미, 동사구 의미, 등에 대해서도 마찬가지입니다. 그것은 역시 자동사, 타동사, 또는 이중타동사에도 적용될 수 있습니다. 적절하게 유연한, and 전형적으로 이들 다른 유형의 의미를 인수로 취할 수 있도록 정의되는 그것에 대해 단일 표시를 제공하기 위한 것입니다. 이것은 문장을 결합하는 간단한 경우에 대해 정의하고, 그런-다음 다른 경우를 간단한 경우의 관점에서 재귀적으로 정의함으로써 수행될 수 있습니다.[7]

재귀 문법(recursive grammar)은 재귀 생성 규칙(production rules)을 포함하는 형식 문법입니다.[8]

Recursive humor

A recursive Wikipedia page

재귀는 때때로 컴퓨터 과학, 프로그래밍, 철학, 또는 수학 교과서에서 유머러스하게 사용되며, 일반적으로 순환 정의(circular definition) 또는 자기-참조(self-reference)를 제공함으로써, 이것에서 추정되는 재귀 단계가 기본 사례에 더 가까워지지 않지만, 대신 무한 회귀로 이어집니다. 그러한 책들이 용어집에 다음과 같은 농담 항목을 포함하는 것은 드문 일이 아닙니다:

재귀, 재귀를 참조하십시오.[9]

Brian KernighanDennis Ritchie의 책 The C Programming Language의 일부 판의 색인(index)에서 269페이지에 변형이 있습니다; 색인 항목은 자신을 재귀적으로 참조합니다 ("재귀 86, 139, 141, 182, 202, 269"). 이 농담의 초기 버전은 Laurent Siklóssy에 의한 Let's talk Lisp (1975년 12월 1일 Prentice Hall PTR에 의해 발행, 저작권 날짜 1976년) 및 Kernighan와 Plauger에 의한 Software Tools (Addison-Wesley Professional 발행: 1976년 1월 11일)에서 찾아질 수 있습니다. 그 농담은 역시 Kernighan과 Pike에 의한 The UNIX Programming Environment에 나옵니다. 그것은 The C Programming Language의 초판에는 나오지 않았습니다. 그 농담은 함수형 프로그래밍 민속의 일부이고 앞서 언급한 책이 출판되기 전에 이미 함수형 프로그래밍 커뮤니티에 널리 퍼졌습니다.

또 다른 농담은 "재귀를 이해하기 위해, 당신은 재귀를 이해해야 합니다"라는 것입니다.[9] 구글 웹 검색 엔진의 영어 버전에서, "recursion"에 대해 검색할 때, 사이트에서 "Did you mean: recursion"을 제안합니다.[10] 대안적인 형식은 Andrew Plotkin에서 다음과 같습니다: "If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is."

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

In mathematics

시에르핀스키 삼각형프랙탈(fractal)을 형성하는 삼각형의 닫힌 재귀

Recursively defined sets

Example: the natural numbers

재귀적으로 정의된 집합의 정규 예제는 자연수에 의해 주어집니다:

0은 안에 있습니다.
만약 n 안에 있으면, n + 1은 안에 있습니다.
자연수의 집합은 이전 두 속성을 만족하는 가장 작은 집합입니다.

Example: The set of true reachable propositions

또 다른 흥미로운 예제는 공리적 시스템(axiomatic system)에서 모든 "참에 도달 가능한" 전제의 집합입니다.

  • 만약 전제가 공리이면, 그것은 참에 도달 가능한 전제입니다.
  • 만약 전제가 추론 규칙에 의하여 참에 도달 가능한 전제로부터 획득될 수 있으면, 그것은 참에 도달 가능한 전제입니다.
  • 참에 도달 가능한 전제의 집합은 이들 조건을 만족하는 전제의 가장 작은 집합입니다.

이 집합은 '참에 도달 가능한 전제'라고 불리며 왜냐하면 수학의 기초론에 대한 비-구성적인 접근에서, 참 전제의 집합은 공리와 추론의 규칙으로부터 재귀적으로 구성되는 집합보다 더 클 수 있기 때문입니다. 괴델의 불완전성 정리(Gödel's incompleteness theorems)를 역시 참조하십시오.

Finite subdivision rules

유한 부분 분할 규칙은 프랙탈(fractal)과 같은 이미지를 생성하기 위해서 사용될 수 있는 재귀의 기하학적 형태입니다. 부분 분할 규칙은 유한하게 많은 레이블에 의해 레이블된 다각형의 모임으로 시작하고, 그런 다음 각 다각형은 원래 다각형의 레이블에만 의존하는 방식으로 더 작은 레이블된 다각형으로 부분 분할합니다. 이 프로세스는 반복될 수 있습니다. 칸토어 집합(Cantor set)을 생성하기 위한 표준 `중점 삼분의 일' 기법은 부분 분할 규칙이고, 질량중심 부분 분할(barycentric subdivision)입니다.

Functional recursion

함수(function)는 그 자체의 관점에서 부분적으로 정의될 수 있습니다. 익숙한 예제는 피보나치 숫자(Fibonacci number) 수열: F(n) = F(n − 1) + F(n − 2)입니다. 그러한 정의를 유용하게 사용하기 위해, 비-재귀적으로 정의된 값, 이 경우에서 F(0) = 0 그리고 F(1) = 1으로 이어져야 합니다.

유명한 재귀적 함수는—피보나치 수열과는 달리—재귀 없이 쉽게 표현될 수 없는 아커만 함수(Ackermann function)입니다.

Proofs involving recursive definitions

이전 섹션에서 처럼, 재귀적으로 정의된 집합 또는 함수에 경우에 의한 증명(proof by cases)의 표준 기법을 적용하여, 수학적 논리(mathematical logic)컴퓨터 과학(computer science)에서 증명을 유도하는 것에 널리 사용되는 수학적 귀납법(mathematical induction)의 강력한 일반화, 구조적 귀납법(structural induction)을 산출됩니다.

Recursive optimization

동적 프로그래밍(dynamic programming)은 재귀적 형태로 다중주기 또는 다중단계 최적화 문제를 다르게 말하는 최적화(optimization)에 대한 접근입니다. 동적 프로그래밍의 핵심 결과는 벨먼 방정식(Bellman equation)이며, 이것은 나중 시간 (또는 나중 단계)에서 그의 값의 관점에서 이전 시간 (또는 이전 단계)에서 최적화 문제의 그 값을 씁니다.

The recursion theorem

집합 이론(set theory)에서, 이는 재귀적으로 정의된 함수가 존재한다는 것을 보증하는 정리입니다. 집합 X, X의 원소 a와 함수 가 주어지면, 정리는, 임의의 자연수 n에 대해

를 만족하는 고유한 함수 가 존재하는 것을 말합니다 (여기서 는 영을 포함하는 자연수의 집합을 나타냅니다).

Proof of uniqueness

aX의 원소이고,

을 만족하는 두 함수 그리고 를 취합니다.

그것은 모든 자연수 n에 대해 인 것을 수학적 귀납법(mathematical induction)에 의해 입증될 수 있습니다:

기본 경우: 이고 그래서 등식은 에 대해 유지됩니다.
귀납적 단계: 어떤 에 대해 를 가정합니다. 그러면 입니다.
따라서 F(k) = G(k)는 F(k+1) = G(k+1)를 의미합니다.

귀납법에 의해, 모든 에 대해 입니다.

In computer science

단순화의 공통적인 방법은 문제를 같은 유형의 부분문제로 나누는 것입니다. 컴퓨터 프로그래밍 기법으로서, 이것은 분할과 정복(divide and conquer)이라고 하고 많은 중요한 알고리듬 설계의 핵심입니다. 분할과 정복은 문제 해결에 대한 하향식 접근 방식으로, 여기서 문제는 점점 더 작은 사례를 해결함으로써 해결됩니다. 반대 접근 방식은 동적 프로그래밍입니다. 이 접근 방식은 상향식 접근 방식으로 역할을 하며, 여기서 문제는 원하는 크기에 도달할 때까지 점점 더 큰 인스턴스를 해결함으로써 해결됩니다.

재귀의 고전적인 예제는 여기 C 코드에서 제공되는 팩토리얼(factorial) 함수의 정의입니다:

unsigned int factorial(unsigned int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

그 함수는 더 작은 버전의 입력 (n - 1)에서 자신을 재귀적으로 호출하고 팩토리얼의 수학적 정의와 유사하게 기본 경우에 도달할 때까지 재귀 호출의 결과에 n을 곱합니다.

컴퓨터 프로그래밍에서 재귀는 함수가 더 단순하고 종종 더 작은 버전의 자체로 정의될 때 예시됩니다. 문제에 대한 해는 그런-다음 문제의 더 간단한 버전에서 얻어진 해를 결합함으로써 고안됩니다. 재귀의 한 가지 예제 응용 프로그램은 프로그래밍 언어에 대한 파서에 있습니다. 재귀의 가장 큰 장점은 가능한 문장, 설계, 또는 다른 데이터의 무한한 집합이 유한 컴퓨터 프로그램에 의해 정의, 구문 분석 또는 생성될 수 있다는 것입니다.

재귀 관계는 하나 이상의 수열을 재귀적으로 정의하는 방정식입니다. 특정 종류의 재귀 관계의 일부는 비재귀적 정의 (예를 들어, 닫힌-형식 표현)를 얻기 위해 "해결"될 수 있습니다.

알고리듬에서 재귀의 사용은 장점과 단점 둘 다를 가집니다. 주요 이점은 보통 지침의 단순성입니다. 주요 단점은 재귀 알고리듬의 메모리 사용량이 매우 빠르게 증가하여, 더 큰 인스턴스에 대해 비실용적으로 그것들을 렌더링하는 것입니다.

In biology

하나의 큰 부분이 두 개 이상의 유사한 작은 부분으로 분기되는 분기 구조와 같이 재귀 과정에 의해 생성된 것처럼 보이는 모양이 식물과 동물에 때때로 나타납니다. 한 가지 예는 로마네스코 브로콜리입니다.[11]

In art

Recursive dolls: the original set of Matryoshka dolls by Zvyozdochkin and Malyutin, 1892
Front face of Giotto's Stefaneschi Triptych, 1320, recursively contains an image of itself (held up by the kneeling figure in the central panel).

러시아 인형 또는 마트료시카 인형은 재귀 개념의 물리적 예술적 예입니다.[12]

재귀는 1320년에 만들어진 조토(Giotto)Stefaneschi Triptych 이후로 그림에 사용되어 왔습니다. 그것의 중앙 패널은 Triptych 자체를 제물로 들고 있는 스테파네스키 추기경의 무릎을 꿇고 있는 모습이 포함되어 있습니다.[13]

M. C. EscherPrint Gallery (1956)는 그림을 재귀적으로 포함하는 갤러리를 포함하는 왜곡된 도시를 묘사하는 판화이고, 따라서 ad infinitum입니다.[14]

See also

References

  1. ^ "Definition of RECURSIVE". www.merriam-webster.com. Retrieved 2019-10-24.
  2. ^ Pinker, Steven (1994). The Language Instinct. William Morrow.
  3. ^ Pinker, Steven; Jackendoff, Ray (2005). "The faculty of language: What's so special about it?". Cognition. 95 (2): 201–236. CiteSeerX 10.1.1.116.7784. doi:10.1016/j.cognition.2004.08.004. PMID 15694646. S2CID 1599505.
  4. ^ Nordquist, Richard. "What Is Recursion in English Grammar?". ThoughtCo. Retrieved 2019-10-24.
  5. ^ Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene (2009). "Evidence and argumentation: A reply to Everett (2009)" (PDF). Language. 85 (3): 671–681. doi:10.1353/lan.0.0140. S2CID 16915455. Archived from the original (PDF) on 2012-01-06.
  6. ^ Drucker, Thomas (4 January 2008). Perspectives on the History of Mathematical Logic. Springer Science & Business Media. p. 110. ISBN 978-0-8176-4768-1.
  7. ^ Barbara Partee and Mats Rooth. 1983. In Rainer Bäuerle et al., Meaning, Use, and Interpretation of Language. Reprinted in Paul Portner and Barbara Partee, eds. 2002. Formal Semantics: The Essential Readings. Blackwell.
  8. ^ Nederhof, Mark-Jan; Satta, Giorgio (2002), "Parsing Non-recursive Context-free Grammars", Proceedings of the 40th Annual Meeting on Association for Computational Linguistics (ACL '02), Stroudsburg, PA, USA: Association for Computational Linguistics, pp. 112–119, doi:10.3115/1073083.1073104.
  9. ^ a b Hunter, David (2011). Essentials of Discrete Mathematics. Jones and Bartlett. p. 494. ISBN 9781449604424.
  10. ^ "recursion - Google Search". www.google.com. Retrieved 2019-10-24.
  11. ^ "Picture of the Day: Fractal Cauliflower". 28 December 2012. Retrieved 19 April 2020.
  12. ^ Tang, Daisy. "Recursion". Retrieved 24 September 2015. More examples of recursion: Russian Matryoshka dolls. Each doll is made of solid wood or is hollow and contains another Matryoshka doll inside it.
  13. ^ "Giotto di Bondone and assistants: Stefaneschi triptych". The Vatican. Retrieved 16 September 2015.
  14. ^ Cooper, Jonathan (5 September 2007). "Art and Mathematics". Retrieved 5 July 2020.

Bibliography

External links