여기에서 꼬리 재귀를 사용하면 어떤 이점이 있습니까?

Question 1

꼬리 재귀 함수 호출을 통해 컴파일러는 일반적으로 정기적으로 재귀로 할 수없는 특수 최적화를 수행 할 수 있습니다. 꼬리 재귀 함수에서, 재귀 호출은 마지막으로 실행 된 것입니다. 이 경우, 각 호출에 대한 스택 프레임을 할당하는 대신 컴파일러는 코드를 재 작업하여 현재 스택 프레임을 재사용 할 수 있습니다. 즉, 테일 리퍼 시브 기능은 수백 또는 수천과 달리 단일 스택 프레임 만 사용합니다.

이 최적화는 컴파일러가 일단 꼬리 재귀 호출이 이루어지면 더 이상 실행할 코드가 없기 때문에 이전 변수 사본이 필요하지 않다는 것을 알고 있기 때문에 가능합니다. 예를 들어, 인쇄 명령문이 재귀 통화를 따르는 경우, 컴파일러는 재귀 통화가 반환 된 후 인쇄 할 변수의 값을 알아야하므로 스택 프레임을 재사용 할 수 없습니다.

이 "공간 절약"및 스택 재사용 방법에 대한 자세한 내용에 대한 자세한 정보를 원한다면 Wiki 페이지는 다음과 같습니다. 꼬리 통화

편집 : 나는 이것이 QuickSort에 어떻게 적용되는지 설명하지 않았습니까? 글쎄, 일부 용어는 그 기사에서 모든 것을 혼란스럽게 만드는 기사에서 던져졌습니다 (그리고 그 중 일부는 명백한 잘못입니다). 주어진 첫 번째 함수 (QuickSort)는 왼쪽에 재귀 호출을하고 오른쪽에 재귀 호출을 한 다음 종료합니다. 오른쪽의 재귀 호출은 기능에서 발생하는 마지막 일입니다. 컴파일러가 꼬리 재귀 최적화를 지원하는 경우 (위에서 설명) 왼쪽 호출 만 새 스택 프레임을 만듭니다. 모든 올바른 호출은 현재 프레임을 재사용합니다. 이것은 저장할 수 있습니다 약간 스택 프레임이지만, 파티션이 꼬리 재귀 최적화가 중요하지 않은 일련의 통화를 생성하는 경우에도 여전히 어려움을 겪을 수 있습니다. 또한 오른쪽 통화는 동일한 프레임을 사용하더라도 왼쪽 통화는 이내에 오른쪽 통화는 여전히 스택을 사용합니다. 최악의 경우 스택 깊이는 N입니다.

설명 된 두 번째 버전은 다음과 같습니다 ~ 아니다 꼬리 재귀 퀵조트이지만 오히려 왼쪽 정렬 만 재귀 적으로 수행되고 루프를 사용하여 오른쪽 정렬이 수행되는 퀵조트입니다. 실제로,이 QuickSort (이전에 다른 사용자가 이전에 설명한대로)는 재귀 호출이 마지막으로 실행되는 것이 아니기 때문에 Tail Recursion Optimization을 적용 할 수 없습니다. 이것은 어떻게 작동합니까? 올바르게 구현하면 QuickSort에 대한 첫 번째 호출은 원래 알고리즘의 왼쪽 호출과 동일합니다. 그러나 오른쪽 재귀 호출도 호출되지 않습니다. 이것은 어떻게 작동합니까? 글쎄, 루프는 다음을 처리합니다. 오른쪽의 왼쪽. 정말 말도 안되는 소리이지만 기본적으로 많은 레프를 정렬하면 권리가 단일 요소가되고 정렬 될 필요가 없습니다. 이것은 올바른 재귀를 효과적으로 제거하여 기능을 덜 재귀 적으로 만듭니다. 그러나 실제 구현은 매번 왼쪽 만 선택하지 않습니다. 가장 작은면을 선택합니다. 아이디어는 여전히 동일합니다. 기본적으로 두 가지 대신 한쪽에 재귀적인 호출 만 수행합니다. 짧은면을 선택하면 스택 깊이가 적절한 바이너리 트리의 깊이 인 Log2 (N)보다 결코 더 크지 않도록합니다. 짧은면이 항상 현재 배열 섹션의 크기의 절반이 될 것이기 때문입니다. 그러나 기사에 의해 주어진 구현은 "왼쪽은 전체 트리"라는 동일한 최악의 시나리오로 어려움을 겪을 수 있기 때문에 이것을 보장하지는 않습니다. 이 기사는 실제로 더 많은 독서를 할 의향이 있다면 실제로 그것에 대한 좋은 설명을 제공합니다. QuickSort를 기반으로 한 효율적인 선택 및 부분 정렬

Question 2

"혼합 재귀/반복"버전의 요점, 즉 재귀로 하나의 하위 범위를 처리하고 반복에 의한 다른 하위 범위를 처리하는 버전의 장점은 재귀 적으로 처리 할 수있는 두 가지 하위 범위 중 어느 것을 선택함으로써 재귀 깊이가 결코 초과되지 않을 것이라고 보장하십시오 log2 N, 피벗 선택이 얼마나 나쁜지에 관계없이.

용 TAIL-RECURSIVE-QUICKSORT 이 질문에 제공된 의사 코드는 재귀 처리가 문자 그대로 재귀적인 호출에 의해 먼저 수행되는 경우, 재귀 호출이 주어져야합니다. 짧은 하위 범위. 그 자체로는 재귀 깊이가 log2 N. 따라서 재귀 깊이를 달성하기 위해서는 재귀 호출을 통해 처리 할 하위 범위를 결정하기 전에 코드가 하위 범위의 길이를 절대적으로 비교해야합니다.

해당 접근법의 적절한 구현은 다음과 같이 보일 수 있습니다 (유사 코드를 출발점으로 빌리십시오).

HALF-RECURSIVE-QUICKSORT(A, p, r)
   while p < r
      q = PARTITION(A, p, r)
      if (q - p < r - q)
        HALF-RECURSIVE-QUICKSORT(A, p, q-1)
        p = q+1
      else
        HALF-RECURSIVE-QUICKSORT(A, q+1, r)
        r = q-1

그만큼 TAIL-RECURSIVE-QUICKSORT 제공 한 의사 코드는 하위 범위의 길이를 비교하려는 시도를하지 않습니다. 그러한 경우에는 어떤 이익도 제공하지 않습니다. 그리고 아니, 그것은 실제로 "꼬리 재귀"가 아닙니다. QuickSort는 테일 리퍼 시브 알고리즘으로 줄일 수 없습니다.

"Qsort Loguy Higuy"라는 용어에 대한 Google 검색을 수행하는 경우 두 하위 범위 중 하나에 대해서만 재귀를 사용하는 동일한 아이디어를 기반으로 다른 인기있는 QuickSort 구현 (C Standard Library Style)의 수많은 인스턴스를 쉽게 찾을 수 있습니다. . 32 비트 플랫폼의 구현은 재귀 깊이가 그보다 더 높지 않을 수 있기 때문에 구체적으로 ~ 32의 최대 깊이의 명시 적 스택을 사용합니다. (마찬가지로 64 비트 플랫폼은 ~ 64의 스택 깊이 만 필요합니다.)

그만큼 QUICKSORT 피벗의 반복적 인 나쁜 선택이 최대까지 매우 높은 재귀 깊이에 도달 할 수 있기 때문에 두 문자 그대로의 재귀 호출을 만드는 버전 N 최악의 경우. 두 개의 재귀 통화를 사용하면 재귀 깊이가 제한 될 것이라고 보장 할 수 없습니다. log2 N. 스마트 컴파일러가 후행 호출을 대체 할 수 있습니다. QUICKSORT 반복으로, 즉, 당신을 돌립니다 QUICKSORT 당신의 TAIL-RECURSIVE-QUICKSORT, 그러나 하위 범위 길이 비교를 수행하기에 충분히 똑똑하지는 않습니다.

Question 3

테일 리퍼션 사용의 장점 : = 컴파일러가 코드를 최적화하고 비수체 코드로 변환하도록합니다.

재귀 코드에 대한 비수체 코드의 장점 : = 비 재구성 코드는 재귀적인 것보다 실행하는 데 더 적은 메모리가 필요합니다. 이것은 재귀가 소비하는 유휴 스택 프레임 때문입니다.

여기에 흥미로운 부분이 있습니다 :- 컴파일러에도 불구하고 ~할 수 있다 이론은 그 최적화를 수행하지만 실제로는 그렇지 않습니다. Dot-Net 및 Java와 같은 광범위한 컴파일러조차도 최적화를 수행하지 않습니다.

모든 코드 최적화가 직면 한 한 가지 문제는 디버그 가능성의 희생입니다. 최적화 된 코드는 더 이상 소스 코드에 해당하지 않으므로 스택 추적 및 예외 세부 사항을 쉽게 이해할 수 없습니다. 고성능 코드 또는 과학 응용 프로그램은 한 가지이지만 릴리스 후에도 대부분의 소비자 응용 프로그램 디버깅이 필요합니다. 따라서 최적화는 그렇게 활발하게 수행되지 않습니다.

참조하십시오 :

Question 4

여기에는 어휘 혼란이있는 것 같습니다.

첫 번째 버전은 Tail Recursive입니다. 마지막 진술은 재귀적인 호출이기 때문입니다.

QUICKSORT(A, p, r)
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

재귀를 루프로 변환하는 테일 리퍼션 최적화를 적용하면 두 번째를 얻을 수 있습니다.

TAIL-RECURSIVE-QUICKSORT(A, p, r)
  while p < r
    q = PARTITION(A, p, r)
    TAIL-RECURSIVE-QUICKSORT(A, p, q-1)
    p = q+1

이것의 이점은 일반적으로 스택 메모리가 줄어든다는 것입니다. 왜 그런 겁니까? 이해하려면 31 개의 항목으로 배열을 정렬하고 싶다고 상상해보십시오. 모든 파티션이 완벽 할 가능성이 거의없는 경우, 즉, 배열을 중간에 바로 분할하고, 재귀 깊이는 4가 될 것입니다. 실제로, 첫 번째 분할은 15 개의 항목의 두 개의 파티션, 두 번째는 7 개의 항목의 두 파티션을 생성합니다. 세 번째는 3 개의 항목 중 두 개이며 네 번째 후에는 모든 것이 분류됩니다.

그러나 파티션은 거의 완벽하지 않습니다. 결과적으로 모든 재귀가 똑같이 깊어지지는 않습니다. 이 예에서는 일부 레벨이 깊고 일부는 7 개 이상 (최악의 경우는 30)을 가질 수 있습니다. 재귀의 절반을 제거하면 최대 재귀 깊이가 줄어들 가능성이 높습니다.

Andreyt가 지적했듯이, 종종 가장 큰 파티션이 항상 반복적으로 처리되고 가장 작은 범위를 재귀 적으로 비교하기 위해 종종 범위가 비교됩니다. 이는 주어진 입력 및 피벗 선택 전략에 대한 가능한 가장 작은 재귀 깊이를 보장합니다.

그러나 이것이 항상 그런 것은 아닙니다. 때때로 사람들은 가능한 빨리 결과를 산출하거나 첫 번째 N 요소 만 찾고 정렬하기를 원합니다. 이 경우 그들은 항상 두 번째 파티션 전에 첫 번째 파티션을 정렬하고자합니다. 이 상황에서도 꼬리 재귀를 제거하면 일반적으로 메모리 사용량이 향상되며 결코 악화되지 않습니다.

Question 5

나는 이것이이 의심을 요청하기에 올바른 장소인지 정확히 모른다. 아니면 새로운 질문을 게시해야했지만 나는 매우 비슷한 의심을 가지고있다.



void print(int n) {
  if (n < 0) return;
  cout << " " << n;
// The last executed statement is recursive call
  print(n-1);
  print(n-1);
}

이 꼬리는 재귀입니까?

Question 6

꼬리 재귀는 Tail Call 제거라는 최신 컴파일러에 의해 수행 된 최적화입니다. 호출자/학부모 기능이 하위 호출이 완료된 후 풀기 단계에서해야 할 일이 없으면 마지막으로 재귀 호출 자체가되고 최신 컴파일러는 GOTO와 라벨을 사용하여 최적화를 위해 라벨을 사용합니다.

예 : 우리 버전 -> 인쇄 n에서 1

void fun(int n){
if(n==0)
return;
printf("%d\n",n);
fun(n-1)
}

최적화 후->

void fun(int n){
start:
if(n==0)
return;
printf("%d\n",n);
n=n-1;
goto start;
}

이 최적화의 장점 : 1. 테일 수익성 호출에 대한 스택 프레임은 거의 없습니다. 3. 더 많은 분할 오류는 C/C ++이고 Java의 스택 오버 플로우는 없습니다.