재귀 알고리즘을 꼬리 재귀 알고리즘으로 바꾸려면 어떻게해야합니까?

Question

병합 정렬에 들어가기위한 첫 번째 시도로서 문자열에 대해 작동하는 다음 코드를 처리했습니다. 처리 할 목록보다 쉽기 때문입니다. 최적화의 가능성에 대해 위키 백과에 읽기

class Program 
{ 
    static int iterations = 0; 
    static void Main(string[] args) 
    {    
     string test = "zvutsrqponmlihgfedcba"; 
     test = MergeSort(test); 
     // test is sorted after 41 iterations 
    } 

    static string MergeSort(string input) 
    { 
     iterations++; 
     if (input.Length < 2) 
      return input; 
     int pivot = 0; 
     foreach (char c in input) 
      pivot += c; 
     pivot /= input.Length; 
     string left = ""; 
     string right = ""; 
     foreach (char c in input)    
      if (c <= (char)pivot) 
       left += c; 
      else 
       right += c;    
     return string.Concat(new string[] { MergeSort(left), MergeSort(right) }); 
    } 
} 

나는 다음과 같은 힌트 "공간이 사용됩니다 (N 로그) O는, 배열의 작은 절반으로 첫 번째 재귀 최대 있는지 확인하고 재귀하는 꼬리 호출을 사용하려면 발견 다른쪽에. " 솔직히 이걸 내 사건에 적용하는 방법을 모르겠다. 재귀 및 계승에 관해 배울 때 IT 클래스의 꼬리 호출에 대한 막연한 기억이 있습니다. 그러나 위키 백과의 조언을 코드 조각에 적용하는 방법을 실제로 이해할 수 없습니다.

도움을 주시면 감사하겠습니다.

Answer 1

하면 이것은 QuickSort의 매우 느린 버전을 구현하지만, 머지 소트에 대한 질문을 한 사실로 시작하는이 질문에 많은 문제가 있습니다 : 당신은이 부분의 C#을 동등한 누락되었습니다. 일반적으로 MergeSort는 꼬리 재귀 알고리즘으로 구현되지 않습니다.

나를 대신에 더 나은 질문을 물어 보자 :

을 나는 꼬리 재귀 알고리즘에 재귀 알고리즘을 설정하려면 어떻게합니까?

좀 더 간단한 꼬리 재귀 변형을 스케치하고 나면이를 적용하는 방법을 알아낼 수 있습니다. 그렇다면 그렇게하는 것이 좋습니다. 이 이전과 같은 프로그램이 정확하게 것을

static int Count(Tree tree) 
{ 
    int total = 0; 
    Tree current = tree; 
    if (current.IsEmpty) 
     return 0; 
    total += 1; 
    int countLeft = Count(current.Left); 
    total += countLeft; 
    current = current.Right; 
    int countRight = Count(current); 
    total += countRight; 
    return total; 
} 

주의 사항 :

static int Count(Tree tree) 
{ 
    if (tree.IsEmpty) 
     return 0; 
    return 1 + Count(tree.Left) + Count(tree.Right); 
} 

하는의는 다음과 같은 다소 기괴한 변환을 사용하여 더 많은 단계로 그를 분해하자

는 다음과 같은 재귀 알고리즘을 가지고 가정 더 자세한. 물론 프로그램을 그렇게 장황하게 작성하지는 않겠지 만 재귀 적으로 재귀 적으로 만들 수 있습니다.

꼬리 재귀 지점은 재귀 호출을 goto로 바꾸는 것입니다. 우리는 다음과 같이 할 수 있습니다 :

static int Count(Tree tree) 
{ 
    int total = 0; 
    Tree current = tree; 

Restart: 

    if (current.IsEmpty) 
     return total; 
    int countLeft = Count(current.Left); 
    total += 1; 
    total += countLeft; 
    current = current.Right; 
    goto Restart; 
} 

우리가 해왔 던 것을보십시오. 재귀 대신에 누적 기의 상태를 유지하면서 재귀 적으로 현재 참조를 재설정하고 처음으로 돌아갑니다.

이제 QuickSort 알고리즘과 동일한 작업을 수행하는 방법이 명확합니까?

Answer 2

이것은 MergeSort가 아닌 QuickSort의 최적이 아닌 변형입니다.

function merge(left, right) 
    var list result 
    while length(left) > 0 or length(right) > 0 
     if length(left) > 0 and length(right) > 0 
      if first(left) <= first(right) 
       append first(left) to result 
       left = rest(left) 
      else 
       append first(right) to result 
       right = rest(right) 
     else if length(left) > 0 
      append first(left) to result 
      left = rest(left) 
     else if length(right) > 0 
      append first(right) to result 
      right = rest(right) 
    end while 
    return result