C ++의 꼬리 재귀

C ++의 꼬리 재귀

---

누군가가 C ++로 간단한 꼬리 재귀 함수를 보여줄 수 있습니까?

꼬리 재귀가 더 좋은 이유는 무엇입니까?

꼬리 재귀 외에 어떤 종류의 재귀가 있습니까?

---

간단한 꼬리 재귀 함수 :

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

꼬리 재귀는 기본적으로 다음과 같은 경우입니다.

• 재귀 호출이 하나뿐입니다.
• 그 호출은 함수의 마지막 문입니다.

좋은 컴파일러가 재귀를 제거하여 루프로 변환 할 수 있다는 점을 제외하고는 "더 나은"것은 아닙니다. 이것은 더 빠를 수 있으며 확실히 스택 사용량을 절약 할 수 있습니다. GCC 컴파일러는이 최적화를 수행 할 수 있습니다.

---

C ++의 꼬리 반향은 C 또는 다른 언어와 동일하게 보입니다.

void countdown( int count ) {
    if ( count ) return countdown( count - 1 );
}

꼬리 재귀 (및 일반적으로 꼬리 호출)는 꼬리 호출을 실행하기 전에 호출자의 스택 프레임을 지워야합니다. 와 프로그래머에, 꼬리 재귀 루프와 유사하다 return처럼 작동 감소 goto first_line;. 하지만 컴파일러는 사용자가 수행중인 작업을 감지해야하며 그렇지 않은 경우 여전히 추가 스택 프레임이 있습니다. 대부분의 컴파일러는이를 지원하지만 루프를 작성하거나 goto일반적으로 더 쉽고 덜 위험합니다.

비재 귀적 마무리 호출은 goto더 독특한 기능인 임의 분기 ( 다른 함수의 첫 번째 행 과 같은) 를 활성화 할 수 있습니다 .

C ++에서는 return명령문 범위에 사소하지 않은 소멸자가있는 개체가있을 수 없습니다 . 함수 끝 정리를 수행하려면 피 호출자가 호출자에게 다시 돌아가서 마무리 호출을 제거해야합니다.

또한 꼬리 재귀를 사용하려면 각 단계에서 함수 인수 목록을 통해 알고리즘의 전체 상태를 전달해야합니다 (모든 언어). (이것은 다음 호출이 시작되기 전에 함수의 스택 프레임을 제거해야한다는 요구 사항에서 분명합니다. 지역 변수에 데이터를 저장할 수 없습니다.) 또한 꼬리가 반환되기 전에 함수의 반환 값에 어떤 작업도 적용 할 수 없습니다. .

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

---

꼬리 재귀는 꼬리 호출의 특별한 경우입니다. 마무리 호출은 컴파일러가 호출 된 함수에서 반환 할 때 수행해야 할 작업이 없음을 확인할 수있는 곳입니다. 본질적으로 호출 된 함수의 반환을 자신의 것으로 바꿉니다. 컴파일러는 종종 몇 가지 스택 수정 작업을 수행 한 다음 호출하는 대신 호출 된 함수의 첫 번째 명령어 주소 로 점프 할 수 있습니다 .

일부 리턴 콜을 제거하는 것 외에 이것에 대한 가장 좋은 점 중 하나는 스택 사용량도 줄인다는 것입니다. 일부 플랫폼 또는 OS 코드에서는 스택이 상당히 제한 될 수 있으며 데스크탑의 x86 CPU와 같은 고급 시스템에서는 이와 같이 스택 사용량을 줄이면 데이터 캐시 성능이 향상됩니다.

꼬리 재귀는 호출 된 함수가 호출 함수와 동일한 위치입니다. 이것은 위에서 언급 한 꼬리 호출 최적화의 점프와 정확히 동일한 루프로 전환 될 수 있습니다. 이것은 동일한 기능 (callee 및 caller)이므로 점프 전에 수행해야하는 스택 수정이 적습니다.

다음은 컴파일러가 루프로 전환하기가 더 어려운 재귀 호출을 수행하는 일반적인 방법을 보여줍니다.

int sum(int a[], unsigned len) {
     if (len==0) {
         return 0;
     }
     return a[0] + sum(a+1,len-1);
}

이것은 많은 컴파일러가 어차피 알아낼 수있을만큼 간단하지만, 호출 된 합계에서 반환 된 후 숫자가 반환 된 후에 발생해야하는 추가가 있으므로 간단한 마무리 호출 최적화가 불가능합니다.

그랬다면 :

static int sum_helper(int acc, unsigned len, int a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(int a[], unsigned len) {
     return sum_helper(0, len, a);
}

꼬리 호출 인 두 함수 모두에서 호출을 활용할 수 있습니다. 여기서 sum 함수의 주요 작업은 값을 이동하고 레지스터 또는 스택 위치를 지우는 것입니다. sum_helper는 모든 수학을 수행합니다.

질문에서 C ++를 언급 했으므로 이에 대한 몇 가지 특별한 사항을 언급하겠습니다. C ++는 C가하지 않는 것을 숨 깁니다. 이러한 소멸자 중 꼬리 호출 최적화를 방해하는 주요 요소가 있습니다.

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    return z.baz();
}

이 예에서 baz에 대한 호출은 baz에서 반환 된 후 z를 소멸해야하므로 실제로 꼬리 호출이 아닙니다. C ++의 규칙은 다음과 같이 호출 기간 동안 변수가 필요하지 않은 경우에도 최적화를 더 어렵게 만들 수 있다고 생각합니다.

int boo(yin * x, yang *y) {
    dharma z = x->foo() + y->bar();
    int u = z.baz();
    return qwerty(u);
}

z는 여기에서 qwerty에서 반환 된 후 파괴되어야 할 수 있습니다.

Another thing would be implicit type conversion, which can happen in C as well, but can more complicated and common in C++. For instance:

static double sum_helper(double acc, unsigned len, double a[]) {
     if (len == 0) {
        return acc;
     }
     return sum_helper(acc+a[0], len-1, a+1);
}
int sum(double a[], unsigned len) {
     return sum_helper(0.0, len, a);
}

Here sum's call to sum_helper is not a tail call because sum_helper returns a double and sum will need to convert that into an int.

In C++ it is quite common to return an object reference which may have all kinds of different interpretations, each of which could be a different type conversion, For instance:

bool write_it(int it) {
      return cout << it;
}

Here there is a call made to cout.operator<< as the last statement. cout will return a reference to itself (which is why you can string lots of things together in a list separated by << ), which you then force to be evaluated as a bool, which ends up calling another of cout's methods, operator bool(). This cout.operator bool() could be called as a tail call in this case, but operator<< could not.

EDIT:

One thing that is worth mentioning is that a major reason that tail call optimization in C is possible is that the compiler knows that the called function will store it's return value in the same place as the calling function would have to ensure that its return value is stored in.

---

Tail recursion is a trick to actually cope with two issues at the same time. The first is executing a loop when it is hard to know the number of iterations to do.

Though this can be worked out with simple recursion, the second problem arises which is that of stack overflow due to the recursive call being executed too many times. The tail call is the solution, when accompanied by a "compute and carry" technique.

In basic CS you learn that a computer algorithm needs to have an invariant and a termination condition. This is the base for building the tail recursion.

1. All computation happens in the argument passing.
2. All results must be passed onto function calls.
3. The tail call is the last call, and occurs at termination.

To simply put it, no computation must happen on the return value of your function .

Take for example the computation of a power of 10, which is trivial and can be written by a loop.

Should look something like

template<typename T> T pow10(T const p, T const res =1)
{
return p ? res: pow10(--p,10*res);
}

This gives an execution, e.g 4:

ret,p,res

-,4,1

-,3,10

-,2,100

-,1,1000

-,0,10000

10000,-,-

It is clear that the compiler just has to copy values without changing the stack pointer and when the tail call happens just to return the result.

Tail recursion is very important because it can provide ready made compile time evaluations, e.g. The above can be made to be.

template<int N,int R=1> struct powc10
{
int operator()() const
{
return  powc10<N-1, 10*R>()();
}
};

template<int R> struct powc10<0,R>
{

int operator()() const
{
return  R;
}

};

this can be used as powc10<10>()() to compute the 10th power at compile time.

Most compilers have a limit of nested calls so the tail call trick helps. Evidently,there are no meta programming loops, so have to use recursion.

---

Tail recursion does not exist really at compiler level in C++.

Although you can write programs that use tail recursion, you do not get the inherit benefits of tail recursion implemented by supporting compilers/interpreters/languages. For instance Scheme supports a tail recursion optimization so that it basically will change recursion into iteration. This makes it faster and invulnerable to stack overflows. C++ does not have such a thing. (least not any compiler I've seen)

Apparently tail recursion optimizations exist in both MSVC++ and GCC. See this question for details.

---

Wikipedia has a decent article on tail recursion. Basically, tail recursion is better than regular recursion because it's trivial to optimize it into an iterative loop, and iterative loops are generally more efficient than recursive function calls. This is particularly important in functional languages where you don't have loops.

For C++, it's still good if you can write your recursive loops with tail recursion since they can be better optimized, but in such cases, you can generally just do it iteratively in the first place, so the gain is not as great as it would be in a functional language.

참고URL : https://stackoverflow.com/questions/2693683/tail-recursion-in-c