재귀(컴퓨터 과학)

로고 프로그래밍 언어를 사용하여 재귀에 크게 의존하는 트리입니다.각 분기는 트리의 작은 버전으로 볼 수 있습니다.

컴퓨터 과학에서, 재귀는 동일한 ^[1][2]문제의 작은 인스턴스에 대한 해결책에 의존하는 계산 문제를 해결하는 방법입니다.재귀는 자체 코드 내에서 자신을 호출하는 함수를 사용하여 이러한 재귀적 문제를 해결합니다.이 접근법은 많은 종류의 문제에 적용될 수 있으며, 재귀는 컴퓨터 ^[3]과학의 중심 아이디어 중 하나이다.

재귀의 힘은 분명히 유한한 문장으로 무한한 객체 집합을 정의할 수 있는 가능성에 있다.마찬가지로 유한 재귀 프로그램에 명시적 반복이 포함되어 있지 않더라도 무한대의 연산이 설명될 수 있다.

--

대부분의 컴퓨터 프로그래밍 언어는 함수가 자체 코드 내에서 자신을 호출할 수 있도록 함으로써 재귀를 지원합니다.일부 기능적 프로그래밍 언어(예:^[5] Clojure)는 루프 구조를 정의하지 않고 코드를 반복적으로 호출하는 재귀에만 의존합니다.계산 가능성 이론에서 이러한 재귀적인 언어만이 튜링 완전하다는 것이 증명되었습니다; 이것은 그들이 제어 구조에 기초하는 명령어만큼 강력하다는 것을 의미합니다 (같은 문제를 해결하기 위해 사용될 수 있습니다.while그리고.for.

내부에서 함수를 반복 호출하면 관련된 모든 콜의 입력 사이즈의 합계와 같은 사이즈의 콜스택이 발생할 수 있습니다.따라서 반복으로 쉽게 해결할 수 있는 문제의 경우 일반적으로 재귀의 효율이 떨어지고 큰 문제의 경우 테일콜 최적화 ^{[citation needed]}등의 최적화 기술을 사용하는 것이 중요합니다.

재귀 함수 및 알고리즘

일반적인 알고리즘 설계 방법은 문제를 원본과 동일한 유형의 하위 문제로 나누고, 이러한 하위 문제를 해결한 후 결과를 결합하는 것입니다.이것은 종종 분할 및 정복 방식이라고 불립니다. 이전에 해결된 하위 문제의 결과를 저장하는 룩업 테이블과 결합하면(반복적으로 문제를 해결하고 추가 계산 시간을 발생시키지 않기 위해), 동적 프로그래밍 또는 메모화라고 할 수 있습니다.

베이스 케이스

재귀함수 정의는 함수가 3회(반복하지 않고) 결과를 생성하는 입력을 의미하는 하나 이상의 기본 케이스와 프로그램이 재귀(호출)하는 입력을 의미하는 하나 이상의 재귀 케이스를 가진다.예를 들어, 요인 함수는 0! = 1 공식과 모든 n > 0, n! = n(n - 1) 공식으로 재귀적으로 정의할 수 있습니다.어느 방정식도 그 자체로 완전한 정의를 구성하지는 않습니다.첫 번째는 베이스 케이스, 두 번째는 재귀 케이스입니다.베이스 케이스는 재귀의 사슬을 끊기 때문에, 「종료 케이스」라고도 불립니다.

재귀 케이스의 작업은 복잡한 입력을 단순한 입력으로 분해하는 것으로 볼 수 있습니다.적절하게 설계된 재귀 함수에서는 재귀 호출마다 입력 문제를 단순화하여 최종적으로 베이스 케이스에 도달해야 합니다(일반적인 상황에서 종료되지 않는 기능(예를 들어 일부 시스템 및 서버 프로세스)은 예외입니다).베이스 케이스의 기입을 게을리하거나 베이스 케이스의 테스트가 잘못되면 무한 루프가 발생할 수 있습니다.

일부 함수(예: e = 1/0! + 1/1! + 1/2! + 1/3! + ...에 대해 직렬을 계산하는 함수)의 경우 입력 데이터에 포함된 명확한 기본 대소문자가 없습니다. 이러한 함수(예: 직렬 예에서 추가할 용어 수)를 추가하여 기본 대소문자를 설정할 수 있습니다.이러한 예는 corecursion에 ^[how?]의해 보다 자연스럽게 처리됩니다.여기서 출력의 연속되는 용어는 부분합입니다.인덱스 파라미터를 사용하여 "n번째 항(n번째 부분합)"을 계산함으로써 재귀로 변환할 수 있습니다.

재귀 데이터 유형

많은 컴퓨터 프로그램은 임의로 대량의 데이터를 처리하거나 생성해야 합니다.재귀는 프로그래머가 정확한 크기를 모르는 데이터를 표현하는 기술입니다. 프로그래머는 이 데이터를 자기 참조 정의로 지정할 수 있습니다.자기반대적 정의에는 귀납적 정의와 공유도적 정의의 두 가지 유형이 있습니다.

유도적으로 정의된 데이터

유도적으로 정의된 재귀 데이터 정의는 데이터의 인스턴스를 구성하는 방법을 지정하는 정의입니다.예를 들어 링크 리스트는 유도적으로 정의할 수 있습니다(여기에서는 Haskell 구문을 사용합니다).

데이터. 리스트 오브 스트링 = 빈 리스트   단점 스트링 리스트 오브 스트링 

위의 코드는 문자열 목록을 비워두거나 문자열과 문자열 목록을 포함하는 구조를 지정합니다.정의의 자체 참조를 통해 임의의 수의 문자열 목록을 구성할 수 있습니다.

귀납적 정의의 또 다른 예는 자연수(또는 양의 정수)입니다.

자연수는 1 또는 n+1입니다.여기서 n은 자연수입니다.

마찬가지로 재귀적 정의는 프로그래밍 언어의 표현식 및 문장의 구조를 모델링하는 데 자주 사용됩니다.언어 설계자는 종종 Backus-Naur 형식과 같은 구문에서 문법을 표현합니다. 곱셈과 덧셈이 포함된 산술 표현의 단순한 언어에 대한 문법은 다음과 같습니다.

 <expr> ::= <번호> (<expr> * <expr>) (<expr> + <expr>)

즉, 표현식은 숫자이거나 두 표현식의 산물이거나 두 표현식의 합이라고 할 수 있습니다.문법은 두 번째와 세 번째 줄의 표현을 반복적으로 참조함으로써 다음과 같은 임의의 복잡한 산술 표현을 허용합니다.(5 * ((3 * 6) + 8))(복수의 곱 또는 합계 연산을 1개의 식에 포함)

데이터 및 코어캐시션을 공유도 가능

유도성 데이터 정의는 데이터에 대해 수행할 수 있는 작업을 지정하는 정의입니다. 일반적으로 무한 크기의 데이터 구조에는 자기 유도성 정의가 사용됩니다.

문자열의 무한 스트림에 대한 공통적인 정의는 비공식적으로 다음과 같습니다.

문자열 스트림은 객체입니다.head는 문자열, tail은 문자열 스트림입니다. 

이는 문자열 목록의 유도 정의와 매우 유사합니다. 이 정의는 데이터 구조의 콘텐츠에 액세스하는 방법, 즉 접근자 기능을 통해 액세스하는 방법을 지정하는 것입니다.head그리고.tail또한 이러한 컨텐츠가 무엇인지도 알 수 있습니다.반면 귀납적 정의는 구조 작성 방법과 구조 작성 원본을 지정합니다.

코어 귀속은 공유도와 관련이 있으며 무한 객체의 특정 인스턴스를 계산하는 데 사용할 수 있습니다.프로그래밍 기술로서, 이것은 느린 프로그래밍 언어의 맥락에서 가장 자주 사용되며, 프로그램 출력의 원하는 크기나 정밀도를 모를 때 재귀보다 선호될 수 있습니다.이러한 경우 프로그램은 무한히 큰(또는 무한정확한) 결과에 대한 정의와 그 결과의 유한 부분을 취하기 위한 메커니즘을 모두 필요로 한다.첫 번째 n개의 소수 계산 문제는 핵심 저주 프로그램으로 해결할 수 있는 문제이다(예: 여기서).

재귀의 종류

단일 재귀 및 다중 재귀

단일 자기 참조만 포함하는 재귀는 단일 재귀라고 하며, 여러 자기 참조를 포함하는 재귀는 다중 재귀라고 합니다.단일 재귀의 표준 예로는 선형 검색과 같은 리스트 트래버설 또는 요인 함수 계산 등이 있으며 다중 재귀의 표준 예로는 깊이 우선 검색과 같은 트리 트래버설이 있습니다.

단일 재귀는 여러 재귀보다 훨씬 효율적이며 일반적으로 선형 시간으로 실행되며 일정한 공간이 필요한 반복 계산으로 대체될 수 있습니다.반면 다중 재귀는 기하급수적인 시간과 공간을 필요로 할 수 있으며, 보다 근본적으로 재귀적이어서 명시적 스택이 없으면 반복으로 대체할 수 없습니다.

여러 재귀가 단일 재귀로 변환될 수 있습니다(필요한 경우 반복으로 변환됩니다).예를 들어, 피보나치 시퀀스의 계산은 순진하게 여러 번 반복을 수반하지만, 각 값에는 두 개의 이전 값이 필요하므로 파라미터로 연속되는 두 개의 값을 전달함으로써 단일 재귀로 계산할 수 있습니다.이것은 corecursion으로 보다 자연스럽게 프레임화되어 초기 값부터 축적되며 각 단계에서 2개의 연속된 값을 추적합니다. corecursion: 예를 참조하십시오.보다 복잡한 예로는 스레드 바이너리 트리를 사용하여 여러 재귀가 아닌 반복 트리 통과를 가능하게 합니다.

간접 재귀

재귀의 가장 기본적인 예와 여기에 제시된 대부분의 예에서는 함수가 자신을 호출하는 직접 재귀가 나타나 있습니다.간접 재귀는 함수 자체가 아니라 함수가 호출한 다른 함수(직접 또는 간접)에 의해 호출될 때 발생합니다.예를 들어 f가 f를 호출하는 경우 f가 f를 호출하는 g를 호출하는 경우 f의 간접 재귀입니다.기능 1은 기능 2, 기능 2는 기능 3을 호출하고 기능 3은 기능 1을 호출하는 등 3개 이상의 기능을 체인으로 할 수 있다.

간접 재귀는 상호 재귀라고도 불리는데, 이것은 단지 강조의 차이일 뿐 다른 개념이 아닙니다.즉, f가 g를 호출한 후 g를 호출한 후 f를 호출하면 f는 간접적으로 재귀하는 반면 g만 보면 간접적으로 재귀하는 반면 f와 g는 상호 재귀하는 것입니다.마찬가지로 서로 호출하는 3개 이상의 함수의 집합을 상호 재귀 함수의 집합이라고 할 수 있습니다.

익명 재귀

재귀는 일반적으로 함수의 이름을 명시적으로 호출함으로써 이루어집니다.단, 현재 컨텍스트에 따라 함수를 암묵적으로 호출함으로써 재귀도 실행할 수 있습니다.이는 익명 함수에 특히 유용하며 익명 재귀로 알려져 있습니다.

구조 재귀와 생성 재귀

일부 저자는 재귀를 "구조적" 또는 "생성적"으로 분류합니다.이 구별은 재귀 프로시저가 작동하는 데이터를 가져오는 위치와 해당 데이터를 처리하는 방식과 관련이 있습니다.

[구조화된 데이터를 소비하는 함수]는 일반적으로 인수를 직접 구조 구성요소로 분해한 다음 해당 구성요소를 처리합니다.직접 구성 요소 중 하나가 입력과 동일한 데이터 클래스에 속할 경우 함수는 재귀적입니다.따라서 이러한 함수를 (구조적으로) 재귀 함수라고 합니다.

--

따라서 구조 재귀 함수의 정의적 특성은 각 재귀 호출에 대한 인수가 원래 입력의 필드 내용이라는 것입니다.구조 재귀에는 XML 처리, 이진 트리 생성 및 검색 등을 포함한 거의 모든 트리 통과가 포함됩니다.자연수의 대수적 구조(즉, 자연수는 0이거나 자연수의 후계자)를 고려함으로써, 계승과 같은 함수도 구조 재귀로 간주될 수 있다.

대신 생성 재귀가 있습니다.

잘 알려진 많은 재귀 알고리즘은 주어진 데이터에서 완전히 새로운 데이터를 생성하고 해당 데이터에서 반복됩니다.HtDP(How to Design Programs)는 이러한 종류를 생성 재귀라고 합니다.생성 재귀의 예로는 gcd, quicksort, 이진 검색, 병합, 뉴턴의 방법, 프랙탈 및 적응 적분 등이 있습니다.

--

이 구별은 기능의 종료를 증명하는 데 중요합니다.

• 유한(유도적으로 정의된) 데이터 구조상의 모든 구조 재귀 함수는 구조 유도를 통해 쉽게 종료되는 것을 나타낼 수 있습니다.직감적으로 각 재귀 호출은 베이스 케이스에 도달할 때까지 더 작은 입력 데이터를 수신합니다.
• 이와는 대조적으로 생성 재귀 함수는 재귀 호출에 더 작은 입력을 제공할 필요가 없기 때문에 종료 증명은 반드시 간단하지 않으며 무한 루프를 회피하는 데 더 많은 주의가 필요합니다.이러한 생성 재귀 함수는 종종 코어 커시티브 함수로 해석될 수 있습니다. 즉, 뉴턴 방법의 연속적인 근사치와 같은 새로운 데이터가 생성되며, 이 코어 커시리얼을 종료하려면 데이터가 결국 어떤 조건을 만족해야 하는데, 이는 반드시 보장되는 것은 아닙니다.
• 루프 변형의 관점에서 구조 재귀는 크기나 복잡성이라는 명백한 루프 변형이 있는 경우로, 유한하게 시작하여 각 재귀 단계에서 감소합니다.
• 반면, 생성재귀는 그러한 명백한 루프 변형이 존재하지 않는 경우이며, 종료는 반드시 0으로 감소하지 않는 "근사 오차"와 같은 함수에 의존하므로 추가 분석 없이 종료가 보장되지 않는다.

구현 문제

실제 구현에서는 순수 재귀 함수(기본 케이스에 대한 단일 검사, 그렇지 않으면 재귀 단계)가 아닌 명확성 또는 효율성을 위해 여러 가지 수정이 이루어질 수 있습니다.여기에는 다음이 포함됩니다.

• 래퍼 기능(위)
• 베이스 케이스의 단락, 일명 "암스-렝스 재귀"(하단)
• 하이브리드 알고리즘(하단)– 데이터가 충분히 작아지면 다른 알고리즘으로 전환

우아함을 바탕으로 랩퍼 기능은 일반적으로 인정되지만, 베이스 케이스의 단락은 특히 학계에서 거부되고 있습니다.하이브리드 알고리즘은 종종 효율성을 위해 사용되며, 작은 경우 재귀의 오버헤드를 줄이기 위해 사용되며, 독립적 재귀는 이러한 특수한 경우입니다.

래퍼 기능

래퍼 함수는 직접 호출되지만 반복되지 않는 함수로, 실제로는 재귀가 이루어지는 별도의 보조 함수를 호출합니다.

래퍼 함수는 파라미터 검증(재귀 함수가 이것들을 건너뛸 수 있도록), 초기화(메모리 할당, 변수 초기화), 특히 메모화를 위한 "재귀 수준" 또는 부분 계산과 같은 보조 변수에 대해 수행할 수 있으며 예외 및 오류를 처리하기 위해 사용할 수 있습니다.중첩된 기능을 지원하는 언어에서는 보조 기능을 래퍼 기능 내에 중첩하여 공유 스코프를 사용할 수 있습니다.네스트된 함수가 없는 경우 보조 함수는 가능하면 개별 함수로, (직접 호출되지 않으므로) 패스 바이 레퍼런스를 사용하여 래퍼 함수와 정보를 공유한다.

베이스 케이스 단락

인트 팩1(인트 n) {    한다면 (n <=> 0)       돌아가다 1;    또 다른       돌아가다 팩1(n-1)*n; } 

정적인 인트 팩2(인트 n) {    // assert(n >= 2);    한다면 (n == 2)       돌아가다 2;    또 다른       돌아가다 팩2(n-1)*n; } 인트 fac2의(인트 n) {    한다면 (n <=> 1)       돌아가다 1;    또 다른       돌아가다 팩2(n); } 

베이스 케이스의 단락은 암의 길이 재귀라고도 불리며, 재귀 콜을 발신하기 전에 베이스 케이스를 체크하는 것으로 구성됩니다.즉, 다음 콜이 베이스 케이스인지 아닌지를 체크하는 것입니다.단락은 특히 효율상의 이유로 즉시 반환되는 함수 호출의 오버헤드를 피하기 위해 이루어집니다.(재귀 스텝 직전에) 베이스 케이스가 이미 체크되어 있기 때문에 개별적으로 체크할 필요는 없지만, 전체적인 재귀가 베이스 케이스 자체에서 시작되는 경우에는 래퍼 기능을 사용해야 합니다.예를 들어 요인 함수에서 기준 케이스는 0! = 1인 반면, 즉시 1을 반환하는 것은 단락 회로이며 0을 놓칠 수 있습니다. 이는 래퍼 함수로 완화할 수 있습니다.상자에는 바로 가기 요인 사례 0 및 1에 대한 C 코드가 표시됩니다.

쇼트 서킷은 함수 호출의 수가 선형적일 수 있는 트리의 늘 포인터와 같이 많은 기본 케이스가 발생할 때 주로 우려되는 사항입니다. 따라서 O(n) 알고리즘의 경우 상당한 절감 효과를 얻을 수 있습니다. 이는 깊이 우선 검색을 위해 아래에 설명되어 있습니다.트리의 단락은 빈 노드를 기본 케이스로 간주하는 것이 아니라 리프(자식이 없는 비어 있지 않은 노드)를 기본 케이스로 간주하는 것에 해당합니다.요인 계산과 같이 기준 사례가 하나뿐인 경우 단락을 통해 O(1)만 절약됩니다.

개념적으로 단락은 재귀 전에만 베이스 케이스를 체크하는 동일한 베이스 케이스와 재귀 스텝을 가지는 것으로 간주할 수 있습니다.또는 리프 노드 r을 고려할 때처럼 다른 베이스 케이스와 보다 복잡한 재귀 스텝(표준 베이스 케이스에서1단계 삭제)을 가지는 것으로 간주할 수 있습니다.트리의 기본 대/소문자로 Null 노드보다 작습니다.단락은 표준 재귀의 베이스 케이스와 재귀 스텝의 명확한 분리에 비해 보다 복잡한 흐름을 가지고 있기 때문에, 특히 ^[8]학계에서는 빈약한 스타일로 간주되는 경우가 많다.

깊이 우선 검색

단락의 기본 예는 이진 트리의 깊이 우선 검색(DFS)에 나와 있습니다. 표준 재귀적 설명은 이진 트리 섹션을 참조하십시오.

DFS의 표준 재귀 알고리즘은 다음과 같습니다.

• 베이스 케이스:현재 노드가 Null이면 false를 반환합니다.
• 재귀 절차: 그렇지 않으면 현재 노드의 값을 확인하고 일치하면 true를 반환하며 그렇지 않으면 하위 노드에서 반복됩니다.

쇼트 서킷에서는, 대신에 다음과 같이 됩니다.

• 현재 노드의 값을 확인하고 일치하는 경우 true를 반환합니다.
• 그렇지 않으면 Null이 아닌 경우 하위 항목에서 반복됩니다.

표준 단계에 대해서는 재귀 단계 전에 기준 케이스 체크를 이동합니다.또는 이들은 각각 다른 형태의 베이스 케이스와 재귀 단계로 간주할 수 있습니다.트리 자체가 비어 있는 경우(루트 노드는 Null)를 처리하려면 래퍼 기능이 필요합니다.

높이 h의 완전한 바이너리 트리의 경우, 자녀로서 2-1개의^h+1h+1 노드와 2개의 늘포인터가 존재하기 때문에(2개의^h Leave마다 2개씩), 최악의 경우 단락으로 함수 호출 수가 절반으로 감소합니다.

C에서 표준 재귀 알고리즘은 다음과 같이 구현될 수 있습니다.

부울 트리_클라이언트(구조 노드 *트리 노드, 인트 i) {     한다면 (트리 노드 == 특수한 순서)         돌아가다 거짓의;  // 베이스 케이스     또 다른 한다면 (트리 노드->데이터. == i)         돌아가다 진실의;     또 다른         돌아가다 트리_클라이언트(트리 노드->왼쪽, i)                   트리_클라이언트(트리 노드->맞다, i); } 

단락 알고리즘은 다음과 같이 실장할 수 있습니다.

// 빈 트리를 처리하는 래퍼 기능 부울 트리_클라이언트(구조 노드 *트리 노드, 인트 i) {     한다면 (트리 노드 == 특수한 순서)         돌아가다 거짓의;  // 빈 트리     또 다른         돌아가다 트리_tree_do(트리 노드, i);  // 보조 함수를 호출합니다. }  // tree_node != NULL로 가정합니다. 부울 트리_tree_do(구조 노드 *트리 노드, 인트 i) {     한다면 (트리 노드->데이터. == i)         돌아가다 진실의;  // 찾았다     또 다른  // 재발         돌아가다 (트리 노드->왼쪽  & & 트리_tree_do(트리 노드->왼쪽,  i))                   (트리 노드->맞다 & & 트리_tree_do(트리 노드->맞다, i)); } 

노드가 유효한(비늘) 경우에만 재귀 호출이 이루어지도록 Boolean &(AND) 연산자의 단락 평가를 사용합니다.AND의 첫 번째 용어는 노드에 대한 포인터이지만 두 번째 용어는 부울이므로 전체 표현은 부울로 평가됩니다.이것은 재귀 단락의 일반적인 관용어입니다.이것은 부울(OR) 연산자의 단락 평가와 더불어 왼쪽 아이에 장애가 발생했을 경우에만 오른쪽 아이만 체크하기 위한 것입니다.실제로 이들 함수의 전체 제어 흐름은 리턴 스테이트먼트에서 단일 부울식으로 대체될 수 있지만 판독성은 효율성에 전혀 도움이 되지 않습니다.

하이브리드 알고리즘

반복적인 함수 호출 및 반환의 오버헤드로 인해 작은 데이터에는 재귀 알고리즘이 비효율적인 경우가 많습니다.이러한 이유로 재귀 알고리즘의 효율적인 구현은 종종 재귀 알고리즘에서 시작되지만 입력이 작아지면 다른 알고리즘으로 전환됩니다.중요한 예로는 병합 정렬이 있습니다. 이 정렬은 종종 데이터가 충분히 작을 때 비재귀적 삽입 정렬로 전환하여 구현됩니다.하이브리드 재귀 알고리즘은 종종 Timsort에서와 같이 하이브리드 병합 정렬/삽입 정렬에서 파생되어 더욱 정교해질 수 있습니다.

재귀와 반복

재귀와 반복은 동일하게 표현됩니다.재귀는 명시적인 콜스택을 사용한 반복으로 대체할 수 있지만 반복은 테일 재귀로 대체할 수 있습니다.어떤 접근방식이 바람직한지는 고려 중인 문제와 사용되는 언어에 따라 달라집니다.필수 프로그래밍에서는 함수 호출 및 콜스택 관리의 오버헤드를 피하기 위해 반복이 특히 단순한 재귀에 선호되지만 재귀는 일반적으로 여러 재귀에 사용됩니다.반면 기능적 언어에서는 테일 재귀 최적화를 통해 오버헤드가 거의 발생하지 않는 재귀가 선호됩니다.반복을 사용한 알고리즘 구현은 쉽지 않을 수 있습니다.

템플릿을 비교하여 x에서_base x = f(n, x_n-1)로 정의된_n x를 계산합니다_n.

n == 기본 반환 x이면 f(n, recursivebase(n-1)를 반환하는 함수 recursive(n)

함수 반복(n) x = ibase = base+1 ~ n x = f(i, x) 반환 x

명령형 언어의 경우 오버헤드는 함수를 정의하는 것이고, 기능 언어의 경우 오버헤드는 누적 변수 x를 정의하는 것입니다.

예를 들어, C에서 요인 함수를 반복 구현하려면 인수를 전달하고 재귀에 의해 값을 반환하는 것이 아니라 루프 인덱스 변수와 어큐뮬레이터 변수에 할당해야 합니다.

서명되어 있지 않다 인트 요인(서명되어 있지 않다 인트 n) {   서명되어 있지 않다 인트 제품. = 1; // 빈 제품은 1입니다.   하는 동안에 (n) {     제품. *= n;     --n;   }   돌아가다 제품.; } 

표현력

오늘날 사용되는 대부분의 프로그래밍 언어에서는 재귀 함수 및 프로시저를 직접 지정할 수 있습니다.이러한 함수가 호출되면 프로그램의 런타임 환경은 함수의 다양한 인스턴스를 추적합니다(다른 메서드를 사용할 수도 있지만 종종 콜 스택을 사용합니다).재귀 호출을 ^[9][10]반복 제어 구성으로 대체하고 프로그램에 의해 명시적으로 관리되는 스택으로 콜 스택을 시뮬레이션함으로써 모든 재귀 함수를 반복 함수로 변환할 수 있다.

반대로, 컴퓨터에 의해 평가될 수 있는 모든 반복 함수와 절차는 (튜링 완전성 참조) 재귀 함수의 관점에서 표현될 수 있다; 루프와 루프를 위한 반복 제어 구조들은 기능적 ^[11][12]언어로 일상적으로 재귀적 형태로 다시 쓰여진다.그러나 실제로는 이 개서가 테일콜 제거에 의존합니다.이것은 모든 언어의 기능은 아닙니다.C, Java 및 Python은 테일콜을 포함한 모든 함수콜이 루프 컨스트럭트를 사용하여 발생하지 않는 스택 할당을 일으킬 수 있는 주요 언어입니다.이러한 언어에서는 테일콜 제거가 다음과 같은 기능인 경우에도 재귀 형식으로 고쳐 쓴 동작 반복 프로그램이 콜스택에 오버플로우 할 수 있습니다.언어 사양에 포함되지 않으며, 동일한 언어의 구현에 따라 테일콜 제거 기능이 다를 수 있습니다.

퍼포먼스 문제

반복 루프 구조를 선호하는 언어(C 및 Java 등)에서는 스택 관리에 필요한 오버헤드와 함수 호출의 상대적인 저속으로 인해 재귀 프로그램과 관련된 시간과 공간 비용이 크게 발생합니다.기능 언어에서 함수 호출(특히 테일 호출)은 일반적으로 매우 빠른 동작입니다.그리고 보통 차이는 덜 눈에 띈다.

구체적인 예로, 위의 "요인" 예제의 재귀적 구현과 반복적 구현 간의 성능 차이는 사용되는 컴파일러에 크게 의존합니다.루프 구조가 선호되는 언어에서는 반복 버전이 재귀 버전보다 몇 배나 더 빠를 수 있습니다.기능적인 언어에서는, 2개의 실장의 전체적인 시간 차이는 무시할 수 있습니다.실제로 작은 수보다 큰 수를 먼저 곱하는 비용이 반복을 선택함으로써 절약되는 시간을 압도할 수 있습니다.

스택 공간

일부 프로그래밍 언어에서는 콜스택의 최대 사이즈가 힙 내에서 사용 가능한 공간보다 훨씬 작습니다.재귀 알고리즘은 반복 알고리즘보다 더 많은 스택공간을 필요로 하는 경향이 있습니다.따라서 이러한 언어들은 스택 오버플로우를 피하기 위해 재귀 깊이에 제한을 둘 수 있습니다. Python도 그러한 언어 ^[13]중 하나입니다.꼬리 재귀의 특수한 경우에 대해서는, 다음의 주의 사항에 주의해 주세요.

취약성

재귀 알고리즘은 스택 오버플로우의 영향을 받을 수 있기 때문에 병리학적 또는 악의적인 ^[14]입력에 취약할 수 있습니다.일부 멀웨어는 프로그램의 콜 스택을 대상으로 하며 스택의 본질적으로 재귀적인 ^[15]특성을 이용합니다.악성코드가 없는 경우에도 무한 재귀로 인한 스택 오버플로는 프로그램에 치명적일 수 있으며 예외 처리 로직은 대응하는 프로세스가 ^[16]종료되는 것을 막지 못할 수 있습니다.

재귀적 문제의 증가

다중 재귀 문제는 추적해야 하는 이전 상태로 인해 본질적으로 재귀적입니다.예를 들어 깊이 우선 검색에서와 같이 트리 트래버설이 있습니다.재귀 메서드와 반복 메서드가 모두 ^[17]사용되지만 리스트 트래버설 및 리스트 선형 검색과 대조됩니다.이것은 단일 재귀 메서드로 자연스럽게 반복됩니다.다른 예로는 Quicksort와 같은 분할 및 정복 알고리즘과 Ackermann 함수와 같은 함수를 들 수 있습니다.이러한 알고리즘은 모두 명시적 스택의 도움을 받아 반복적으로 구현할 수 있지만 스택 관리에 수반되는 프로그래머의 노력과 그 결과 발생하는 프로그램의 복잡성은 반복적인 솔루션의 장점을 능가합니다.

리팩터링 재귀

재귀 알고리즘은 비재귀 ^[18]알고리즘으로 대체할 수 있습니다.재귀 알고리즘을 대체하는 방법 중 하나는 스택 메모리 ^[19]대신 힙 메모리를 사용하여 알고리즘을 시뮬레이션하는 것입니다.대체 알고리즘은 완전히 비재귀적 방법에 기반하여 개발하는 것인데,^[20] 이는 어려울 수 있습니다.예를 들어, Rich Salz의 와일드매트 ^[21]알고리즘과 같은 와일드카드를 일치시키기 위한 재귀 알고리즘이 한때는 일반적이었습니다.크라우스 매칭 와일드카드 알고리즘과 같은 동일한 목적을 위한 비재귀 알고리즘은 재귀의^[22] 결점을 피하기 위해 개발되었으며 테스트 수집 및 프로파일링 ^[23]성능 등의 기술에 기반하여 점진적으로 개선되었습니다.

테일 리커버리 함수

테일 리커버리 함수는 모든 재귀 콜이 테일콜이기 때문에 지연된 동작이 구축되지 않는 함수입니다.예를 들어, gcd 함수(아래에 다시 표시)는 테일 리커시브입니다.반면, 요인 함수(아래도 마찬가지)는 테일 재귀 호출이 테일 위치에 있지 않기 때문에 최종 재귀 호출이 완료된 후에 실행해야 하는 지연 곱셈 연산이 구축됩니다.tail-recursive 호출을 함수 호출이 아닌 점프로 처리하는 컴파일러 또는 인터프리터를 사용하면 gcd와 같은 tail-recursive 함수는 일정한 공간을 사용하여 실행됩니다.따라서 프로그램은 본질적으로 반복적이며, "for" 및 "while" 루프와 같은 명령어 제어 구조를 사용하는 것과 같습니다.

//INPUT: x > = y 및 y > = 0인 정수 x, y 인트 gcd(인트 x, 인트 y) {   한다면 (y == 0)      돌아가다 x;   또 다른      돌아가다 gcd(y, x % y); } 

//INPUT: n은 n >= 0인 정수입니다. 인트 사실(인트 n) {    한다면 (n == 0)       돌아가다 1;    또 다른       돌아가다 n * 사실(n - 1); } 

테일 재귀의 중요성은 테일 재귀 콜(또는 테일 콜)을 발신할 때 발신자의 리턴 위치를 콜스택에 저장할 필요가 없다는 것입니다.재귀 콜이 반환되면 이전에 저장한 리턴 위치로 직접 분기합니다.따라서 테일콜의 이 속성을 인식하는 언어에서는 테일재귀에 의해 공간과 시간이 절약됩니다.

실행순서

다음 두 가지 기능을 고려합니다.

기능 1

무효 재귀 함수(인트 숫자) {     인쇄물(%d\n", 숫자);     한다면 (숫자 < > 4)         재귀 함수(숫자 + 1); } 

기능 2

무효 재귀 함수(인트 숫자) {     한다면 (숫자 < > 4)         재귀 함수(숫자 + 1);     인쇄물(%d\n", 숫자); } 

기능 2는 회선이 교환된 기능1입니다

함수 자체를 1회 호출하는 경우, 재귀 호출 전에 배치된 명령은 재귀 호출 후에 이루어진 명령 전에 재귀별로 1회 실행됩니다.후자는 최대 재귀에 도달한 후 반복적으로 실행됩니다.

또, 인쇄문의 순서는 반대로 되어 있는 것에 주의해 주세요.이는 함수와 문이 콜스택에 저장되어 있기 때문입니다.

재귀적 절차

요인

재귀 절차의 전형적인 예는 자연수의 계수를 계산하는 데 사용되는 함수입니다.

${\displaystyle \operatorname {fact}(n)=param {case}1&{\mbox{if}}n=0\n\cdot \operatorname {fact}(n-1)&{\mbox{if}n>0\end{cases}}}}$

함수 요인:
 입력: n > = 0의 정수 n
 출력: [n × (n-1) × (n-2) × ...× 1]
1. n이 0이면 1을 반환하고, 그렇지 않으면 n × factor(n-1)를 반환합니다.
 말단 요인

함수는 반복 관계로도 쓸 수 있습니다.

${\displaystyle b_{n}=nb_{n-1}}$

${\displaystyle b_{0}=1}$

이 반복관계 평가는 위의 의사코드를 평가할 때 실행되는 계산을 보여줍니다.

b4 = 4 × b3 = 4 × (3 × b21) = 4 × (3 × (1 × b0)) = 4 × (3 × (1 × 1) = 4 × (3 × 1) = 4 × (3 × 2) = 4 × (3 × 2) = 4 × (3 × 2) = 6 = 24

이 요인 함수는 명령형 프로그래밍 언어에서 볼 수 있는 일반적인 루프 구조를 사용하여 재귀 없이 설명할 수도 있습니다.

함수 요인:
 입력: n > = 0의 정수 n
 출력: [n × (n-1) × (n-2) × ...× 1]
1. 값이 1인 running_total이라는 새로운 변수를 만듭니다.
  2. begin loop 1. n이 0이면 루프 2. setrunning_total to (running_total × n) 3. decrementn 4. 반복 루프
 3. returnrunning_total 
 말단 요인

위의 명령 코드는 누적 변수를 사용하는 이 수학적 정의와 동일합니다.

${\displaystyle {displaystyle}\operatorname {fact}(n)&=operatorname {fact_{acc}(n,1)\\operatorname {fact_{acc}}(n,t)&=param{case}t&{\mbox}=0\\\operatorname {fact_{acc}(n})$

위의 정의는 Scheme와 같은 기능적 프로그래밍 언어로 쉽게 변환됩니다.이것은 재귀적으로 구현되는 반복의 예입니다.

최대 공약수

두 정수의 최대공약수를 계산하는 유클리드 알고리즘은 재귀적으로 쓰여질 수 있다.

함수 정의:

${\displaystyle \gcd(x,y)=sys}x&{\mbox{if}}y=0\gcd(y,\operatorname {sys}(x,y)& { \ mbox { } } y > 0 \ \ \ \ end { case } }$

함수 gcd는 다음과 같습니다.input : integer x 、 integer y ( x >0 및 y > = 0)
 1. y가 0이면 returnx 2. 그렇지 않으면 return [gcd(y, (x/y의 복수)]
 end gcd

최대 공약수의 반복 관계입니다${\displaystyle \mathrm{.}}여기$서 x %$$ { $displaystyle$x \ %$y$$$}는${\displaystyle }$x /$y$의 $나머지$를 나타냅니다.

${\displaystyle gcd}$(${\displaystyle x}$ ,${\displaystyle y}$ ) ${\displaystyle =}$ ${\displaystyle gcd}$(${\displaystyle y}$ ,${\displaystyle \mathrm{}x}$ %${\displaystyle y}$) y$$ 0$0{\displaystyle }$ y 0$$${\displaystyle }$、 { $displaystyle$ $\$$gcd$ $( x$ , y ) = \ $gcd$$( y$ , $x$\ %$y$ ) }

$\displaystyle \gcd(x,0)=x}$

gcd(27, 9) = gcd(9, 27 % 9) = gcd(9, 0) = 9

gcd(139, 259) = gcd(259, 111% 259) = gcd(259, 111) = gcd(139, 259% 111) = gcd(37, 111% 37) = gcd(37, 0) = 37

위의 재귀 프로그램은 테일 리커시브입니다.이것은 반복 알고리즘과 동등하며, 위의 계산은 테일 콜을 배제하는 언어에 의해 실행되는 평가 단계를 나타내고 있습니다.다음은 명시적 반복을 사용하는 동일한 알고리즘의 버전으로 테일콜을 배제하지 않는 언어에 적합합니다.변수 x와 y로 상태를 완전히 유지하고 루프 구성을 사용함으로써 프로그램은 재귀 호출을 방지하고 콜 스택을 증가시킵니다.

함수 gcd는 다음과 같습니다.
 입력: 정수 x, x > = y 및 y > = 0인 정수 y
1. 나머지라는 새로운 변수를 만듭니다. 
 2. begin loop 1. y가 0인 경우, 루프 종료 2. x/y의 나머지 3으로 설정. x를 y로 설정 4. y를 나머지 5로 설정. 반복 루프.
 3. 반품 
 end gcd

반복 알고리즘은 일시적인 변수를 필요로 하며, 유클리드 알고리즘에 대한 지식이 주어져도 두 알고리즘의 단계는 매우 유사하지만 단순 검사로 과정을 이해하는 것은 더 어렵다.

하노이의 타워

하노이의 타워

하노이의 탑은 수학 퍼즐로, 그 해답은 ^[24][25]재귀를 보여준다.직경이 다른 디스크 스택을 장착할 수 있는 3개의 페그가 있습니다.큰 디스크는 작은 디스크 위에 쌓이지 않을 수 있습니다.1개의 페그에 n개의 디스크를 장착하고 나서, 그것들을 1개씩 다른 페그로 이동시킬 필요가 있습니다.스택을 이동하기 위한 최소 스텝 수는 몇 개입니까?

함수 정의:

$\displaystyle \operatorname {cases}(n)=param {cases}1&{\mbox{if}}n=1\cdot \operatorname {parames}(n-1)+1&{\mbox{if}n>1\end{cases}}}}$

하노이의 반복 관계:

${\displaystyle h_{n}=2h_{n-1}+1}$

${\displaystyle h_{1}=1}$

하노이(4) = 2×465(3) + 1 = 2×(2×465) + 1 = 2×(2×465) + 1) + 1) + 1 = 2×(2×1+1) + 1 = 2×(2×(3) + 1) + 1 = 2×7 = 1

구현 예:

하노이 함수는 다음과 같습니다.
 입력: n > = 1과 같은 정수 n 
1. n이 1이면 1을 반환합니다.
2. 반환 [2 * [call honosi (n-1)]+ 1]
 하노이를 끝내다

모든 재귀 함수에 명시적 해법이 있는 것은 아니지만 하노이 타워 시퀀스는 명시적 ^[26]공식으로 환원될 수 있다.

h1 = 11 = 2 - 1 h2 = 3 = 22 - 13 h = 73 = 2 - 1 h4 = 15 = 24 - 1 h5 = 315 = 2 - 16 h = 63 = 26 - 17 h = 127 17 1

일반적으로 모든n nn > = 1에 대해 h = 2 - 1

바이너리 검색

바이너리 검색 알고리즘은 각 재귀 패스로 어레이를 반으로 잘라 정렬된 어레이를 단일 요소에 대해 검색하는 방법입니다.여기서 중요한 것은 어레이의 중앙 부근의 중간 지점을 선택하고, 그 지점의 데이터와 검색 중인 데이터를 비교하여 세 가지 조건 중 하나에 대응하는 것입니다.데이터가 중간 지점에 있는지, 중간 지점에 있는 데이터가 검색되는 데이터보다 큰지, 또는 중간 지점에 있는 데이터가 검색되는 데이터보다 작은지 등입니다.위해서.

이 알고리즘에서는 패스마다 오래된 어레이를 반으로 잘라 새로운 어레이가 생성되기 때문에 재귀가 사용됩니다.다음으로 바이너리 검색 프로시저를 재귀적으로 호출합니다.이번에는 새로운 (및 작은) 배열에서 호출합니다.일반적으로 어레이의 크기는 시작 인덱스와 끝 인덱스를 조작하여 조정합니다.알고리즘은 기본적으로 문제 영역을 각 패스로 반으로 나누기 때문에 로그 성장 순서를 나타냅니다.

C에서의 바이너리 검색의 실장 예:

 /* 적절한 초기 조건을 사용하여 binary_search를 호출합니다.  입력: 데이터는 오름차순으로 정렬된 정수 배열입니다. toFind는 검색할 정수입니다. count는 배열에 포함된 요소의 총 수입니다.  출력: binary_search 결과  */  인트 서치(인트 *데이터., 인트 찾기 위해서., 인트 세어보세요)  {     // 시작 = 0 (인덱스 표시)     // 종료 = 카운트 - 1(상단 인덱스)     돌아가다 바이너리_검색(데이터., 찾기 위해서., 0, 세어보세요-1);  }   /* 바이너리 검색 알고리즘.  입력: 데이터는 오름차순으로 정렬된 정수 배열입니다. toFind는 검색할 정수입니다. start는 최소 배열 인덱스입니다. end는 최대 어레이 인덱스입니다. 출력: 어레이 데이터 내에서 찾을 정수 위치, -1(찾을 수 없는 경우) */  인트 바이너리_검색(인트 *데이터., 인트 찾기 위해서., 인트 개시하다, 인트 끝.)  {     //중간점을 가져옵니다.     인트 중앙의 = 개시하다 + (끝. - 개시하다)/2;   //정수 나눗셈       한다면 (개시하다 > 끝.)                     //정지 조건(베이스 케이스)        돌아가다 -1;     또 다른 한다면 (데이터.[중앙의] == 찾기 위해서.)        //찾았다, 인덱스 반환        돌아가다 중앙의;     또 다른 한다면 (데이터.[중앙의] > 찾기 위해서.)         //데이터가 Find보다 큽니다.하반을 검색하세요.        돌아가다 바이너리_검색(데이터., 찾기 위해서., 개시하다, 중앙의-1);     또 다른                                 //데이터가 찾기보다 작습니다.상부를 검색해 주세요.        돌아가다 바이너리_검색(데이터., 찾기 위해서., 중앙의+1, 끝.);  } 

재귀 데이터 구조(구조 재귀)

컴퓨터 과학에서 재귀의 중요한 적용은 목록이나 트리와 같은 동적 데이터 구조를 정의하는 것입니다.재귀 데이터 구조는 런타임 요건에 따라 이론적으로 무한대로 동적으로 확장할 수 있습니다.반대로 정적 배열의 크기는 컴파일 시 설정해야 합니다.

"재귀 알고리즘은 특히 근본적인 문제 또는 처리해야 할 데이터가 재귀적인 ^[27]용어로 정의되어 있는 경우에 적합합니다."

이 섹션의 예에서는 "구조적 재귀"라고 알려진 것을 보여 줍니다.이 용어는 재귀적 프로시저가 재귀적으로 정의된 데이터에 대해 작용하고 있음을 나타냅니다.

프로그래머가 데이터 정의에서 템플릿을 파생하는 한 함수는 구조 재귀를 사용합니다.즉, 함수 본체의 재귀는 주어진 복합값의 ^[7]일부를 즉시 소비합니다.

링크 리스트

다음으로 링크 리스트노드 구조의 C 정의를 나타냅니다.특히 노드가 그 자체로 어떻게 정의되어 있는지 주목해 주십시오.구조 노드의 "다음" 요소는 다른 구조 노드에 대한 포인터이며, 실제로 목록 유형을 만듭니다.

구조 노드 {   인트 데이터.;           // 일부 정수 데이터   구조 노드 *다음 분.;  // 다른 구조 노드에 대한 포인터 }; 

구조 노드 데이터 구조는 재귀적으로 정의되기 때문에 이 구조 노드 데이터 구조에서 작동하는 절차는 재귀적 절차로 자연스럽게 구현될 수 있습니다.다음에 정의된 list_print 절차는 목록이 비워질 때까지 목록을 아래로 이동합니다(즉, 목록 포인터의 값은 NULL).각 노드에 대해 데이터 요소(정수)를 인쇄합니다.C 실장에서는 list_print 프로시저에 의해 리스트는 변경되지 않습니다.

무효 list_print(구조 노드 *목록.) {     한다면 (목록. != 특수한 순서)               // 베이스 케이스     {        인쇄물 (%d, 목록.->데이터.);  // 정수 데이터 뒤에 공백이 표시됩니다.        list_print (목록.->다음 분.);     // 다음 노드의 재귀 호출     } } 

이진 트리

다음은 바이너리 트리 노드에 대한 간단한 정의입니다.링크 리스트의 노드와 마찬가지로 재귀적으로 정의됩니다.좌측(왼쪽 서브트리를 가리키고 있음)과 우측(오른쪽 서브트리를 가리키고 있음)의 2가지 자기 참조 포인터가 있습니다.

구조 노드 {   인트 데이터.;            // 일부 정수 데이터   구조 노드 *왼쪽;   // 왼쪽 서브트리로 포인터   구조 노드 *맞다;  // 오른쪽 서브트리를 가리키다 }; 

트리에 대한 작업은 재귀를 사용하여 구현할 수 있습니다.2개의 자기 참조 포인터(왼쪽과 오른쪽)가 있기 때문에 트리 조작에는 2개의 재귀 콜이 필요할 수 있습니다.

// tree_node에 i가 포함되어 있는지 테스트합니다.포함되어 있는 경우는 1을 반환하고, 포함되지 않은 경우는 0을 반환합니다. 인트 트리_클라이언트(구조 노드 *트리 노드, 인트 i) {     한다면 (트리 노드 == 특수한 순서)         돌아가다 0;  // 베이스 케이스     또 다른 한다면 (트리 노드->데이터. == i)         돌아가다 1;     또 다른         돌아가다 트리_클라이언트(트리 노드->왼쪽, i)    트리_클라이언트(트리 노드->맞다, i); } 

위에서 정의한 대로 tree_contains에 대한 임의의 콜에 대해 최대 2개의 재귀 콜이 이루어집니다.

// 순서대로 통과: 무효 트리_프린트(구조 노드 *트리 노드) {     한다면 (트리 노드 != 특수한 순서) {              // 베이스 케이스         트리_프린트(트리 노드->왼쪽);      // 왼쪽으로 이동         인쇄물(%d, 트리 노드->데이터.);   // 정수 뒤에 공백이 표시됩니다.         트리_프린트(트리 노드->맞다);     // 우회전     } } 

위의 예는 바이너리 트리의 순서대로 트래버설을 나타내고 있습니다.이진 검색 트리는 각 노드의 데이터 요소가 순서대로 있는 이진 트리의 특수한 경우입니다.

파일 시스템 트래버설

파일 시스템의 파일 수는 다를 수 있기 때문에 재귀만이 파일 시스템의 내용을 탐색하고 열거하는 실질적인 방법입니다.파일 시스템 통과는 트리 통과와 매우 유사하므로 트리 통과의 개념은 파일 시스템 통과에 적용할 수 있습니다.구체적으로는, 다음의 코드는, 파일 시스템의 프리 오더 트래버스의 예입니다.

수입품 java.io 를 참조해 주세요.파일;  일반의 학급 파일 시스템 {   일반의 정적인 무효 주된(스트링 [] args) {   횡단하다();  }   /** * 파일 시스템 루트를 가져옵니다. * 재귀 파일 시스템 트래버설을 진행합니다. */  사적인 정적인 무효 횡단하다() {   파일[] fs = 파일.리스트 루트();   위해서 (인트 i = 0; i < > fs.길이; i++) {    시스템..나가..인쇄(fs[i]);    한다면 (fs[i].is 디렉토리() & & fs[i].읽을 수 있다()) {     가로(fs[i]);    }   }  }   /** * 지정된 디렉토리를 재귀적으로 트래버스합니다. * * @traversal fd는 트래버설의 시작점을 나타냅니다. */  사적인 정적인 무효 가로(파일 fd) {   파일[] 금감원 = fd.listFiles();    위해서 (인트 i = 0; i < > 금감원.길이; i++) {    시스템..나가..인쇄(금감원[i]);    한다면 (금감원[i].is 디렉토리() & & 금감원[i].읽을 수 있다()) {     가로(금감원[i]);    }   }  }  } 

이 코드는 재귀와 반복입니다.파일 및 디렉토리가 반복되고 각 디렉토리가 재귀적으로 열립니다.

"rtraverse" 방법은 직접 재귀의 한 예이며, "traverse" 방법은 래퍼 함수입니다.

「베이스 케이스」시나리오에서는, 특정의 파일 시스템내에 항상 고정수의 파일이나 디렉토리가 존재하는 경우가 있습니다.

재귀 알고리즘의 시간 효율

재귀 알고리즘의 시간 효율은 빅 O 표기법의 반복 관계로 나타낼 수 있습니다.그런 다음 (보통) 단일 Big-O 용어로 단순화할 수 있습니다.

바로 가기 규칙(마스터 정리)

함수의 시간 복잡도가 형식인 경우

$${\displaystyle T(n)=a\cdot T(n/b)+f(n)}$$

다음으로 시간 복잡성의 빅 O는 다음과 같습니다.

• ${\displaystyle }$(${\displaystyle n}$ ) ${\displaystyle =O}$ ( ${\displaystyle {n_{}}^{}}$ ${\displaystyle {{log}_{}}^{}}$ b${\displaystyle {{}_{}}^{}}$$a$${\displaystyle {}^{}}$a -${\displaystyle {}^{}{\mathrm{display}}^{}}$ $)$ { $displaystyle$ f ( n ) $= O$ ( $n$^ { \ $log$_ { $b$} $a$- \ $varepsilon }$ }일 $경우{\displaystyle }$ T${\displaystyle }$(${\displaystyle n}$${\displaystyle )}$ $=$ ${\displaystyle \mathrm{E}}$ ($n$ ${\displaystyle {{log}_{}}^{}}$b) $styledisplay$a (n )$\Theta(n^{\log_{b}a}})$
• $f{\displaystyle }$(${\displaystyle n}$ ) ${\displaystyle =\mathrm{\theta }}$ ( ${\displaystyle {n_{}}^{}}$ ${\displaystyle {{log}_{}}^{}}$ b${\displaystyle {{}_{}a}^{}}$a$$) { $displaystyle$ f$(n$) $=$$\Theta(n^{\log$ _${b}a$ $다음$으로 T${\displaystyle (n)}$ $=$${\displaystyle {}^{}}$ ( ${\displaystyle {n_{}}^{}}$ ${\displaystyle {{\log }_{}}^{}}$ b${\displaystyle {{}_{}}^{}\log }$ a log${\displaystyle n}$n$$)(\$style$T(n)=$\Theta(n^{\log _{b}a}\log n)}$
• 몇몇 상수 ε한다면 f(n))Ω(n로그 b⁡+ε){\displaystyle f(n)=\Omega(n^{\log_{b}a+\varepsilon})};0{\displaystyle \varepsilon>0}, 그리고 몇몇 상수 c<>을 ⋅ f(n/b)≤ c⋅ f(n){\displaystylea\cdot f(n/b)\leq c\cdot f(n)}, 1과 모든 충분히 큰, 그때 T(n))Θ. (f(n)$(\displaystyle$$\Theta(f(n)),$

여기서 a는 재귀의 각 레벨에서의 재귀 콜의 수를 나타내고, b는 재귀의 다음 레벨에서의 입력이 얼마나 작은지를 나타냅니다(즉, 문제를 분할하는 부분의 수).f(n)는 재귀의 각 레벨에서 함수가 재귀와 독립적으로 실행하는 작업(파티셔닝, 재결합 등)을 나타냅니다.욕설

「 」를 참조해 주세요.

• 기능 프로그래밍
• 계산 문제
• SQL 계층 및 재귀 쿼리
• 클린-로서의 역설
• 개방 재귀
• 재귀
• 시에르핀스키 곡선
• McCarthy 91 함수
• μ입자 함수
• 원시 재귀 함수
• Tak(함수)

메모들

레퍼런스