꼬리 - 재귀 객체와 함께

Question

나는 꼬리 - 재귀를 만들고 싶습니다 재귀 함수가 있습니다. 내 실제 문제는보다 복잡하고 상황에 따라 다릅니다. 그러나 내가 풀어보고 싶은 문제는 다음과 같은 단순한 프로그램으로 증명됩니다.

#include <iostream> 

struct obj 
{ 
    int n; 

    operator int&() { return n; } 
}; 

int tail(obj n) 
{ 
    return tail(obj{ n + 1 > 1000 ? n - 1000 : n + 1 }); 
} 

int main() 
{ 
    tail(obj{ 1 }); 
} 

이것은 꼬리 재귀라는 것은 당연한 것 같습니다. 그러나 언제든지 obj n의 소멸자가 호출되어야하기 때문에 그렇지 않습니다. 적어도 MSVC13 (편집 : 및 MSVC15)은 이것을 최적화하지 않습니다. obj을 int로 바꾸고 그에 따라 호출을 변경하면 예상대로 꼬리 재귀가됩니다.

내 실제 질문은 다음과 같습니다. obj을 int으로 바꾸는 것 외에이 꼬리 재귀를 만드는 쉬운 방법이 있습니까? 성능 이점을 목표로하고 있으므로 힙 할당 메모리와 new을 가지고 노는 것이 도움이되지 않을 가능성이 큽니다.

Answer 1

임시를 사용하기 때문에 재귀 호출 후에 개체가 필요 없다고 가정합니다.

상당히 해킹 된 해결책 중 하나는 새로 생성 한 객체를 전달하는 재귀 호출을 만들기 전에 객체를 할당하고 포인터를 전달한 다음 재 할당 호출을 다시 할당하는 것입니다.

struct obj 
{ 
    int n; 

    operator int&() { return n; } 
}; 

int tail_impl(obj*& n) 
{ 
    int n1 = *n + 1 > 1000 ? *n - 1000 : *n + 1; 
    delete n; 
    n = new obj{n1}; 
    return tail_impl(n); 
} 

int tail(obj n) 
{ 
    obj *n1 = new obj{n}; 
    auto ret = tail_impl(n1); 
    delete n1; 
    return ret; 
} 

int main() 
{ 
    tail(obj{ 1 }); 
} 

분명히 중요한 예외 안전 세부 사항을 생략했습니다. 그러나 GCC is able to turn tail_impl into a loop, 실제로 꼬리 재귀이기 때문에.

Answer 2

짧은 답변 : 번호

긴 답변 : 당신이 이것을 달성 할 수있는 방법하지만 확실히 쉬운 하나를 찾을 수 있습니다. 표준에서 꼬리 호출 최적화가 필요하지 않으므로 프로그램을 약간만 변경하면 컴파일러가 코드를 최적화하지 못할 수도 있습니다.

더욱 심각한 것은 프로그램을 디버깅해야 할 때 어떻게되는지 생각해보십시오. 컴파일러는 디버거 플래그를 사용하여 고급 테일 호출을 최적화하지 않을 것이므로 프로그램이 릴리스 모드에서만 올바르게 작동합니다. 이렇게하면 프로그램 유지 관리가 훨씬 더 어려워집니다.

꼬리 재귀 대신 그냥 루프를 작성하십시오. 항상 수행 할 수 있으며 훨씬 복잡하지는 않습니다. 또한 힙을 사용하지 않으므로 오버 헤드가 훨씬 적습니다.