이야기의 귀착점

웨이보에서 어떤 사람이 토론의 끝을 맺는 것을 보고 예전에 조씨가 쓴 관련 블로그를 본 것을 떠올렸다. 비교적 상세하게 소개했기 때문에 많은 사람들이 보았을 것이다. 나도 아래에 글을 남겼지만 가시를 돋우어 문장이 관건적인 부분에서 지나갔다는 것을 나타냈다. 조씨는 당연히 이해했다. 그러나 보는 사람이 깊이 생각하지 않으면 진정으로 이해할 수 없다. 다음은 내가 이해한 것을 말하겠다.

무엇이 미귀착입니까

미귀환은 무엇입니까?(tail recursion) 고명사의는 일종의'다른'귀속이다. 그것이 다르다고 하면 먼저 일반적인 귀속을 말해야 한다.일반적인 귀속, 예를 들어 아래의 구급승에 대해 교과서에서 이 함수 호출의 깊이가 너무 깊으면 창고가 터질 위험이 있다는 것을 알려줄 것이다.

//  
int func(int n) { if (n <= 1) return 1; return (n * func(n-1)); }

이유는 많은 사람들이 알고 있기 때문에 함수 호출의 대략적인 과정을 살펴보자.
1) 호출이 시작되기 전에 호출자(또는 함수 자체)는 창고에 관련 데이터, 파라미터, 되돌아오는 주소, 국부 변수 등을 압축한다.
2) 실행 함수.
3) 창고의 관련 데이터를 정리하고 되돌려준다.
따라서 함수 A가 실행될 때 두 번째 단계에서 다른 함수 B를 호출하고 B는 C를 호출한다.창고는 끊임없이 증가하고 끊임없이 데이터를 불러온다. 이 호출 체인이 깊을 때 창고가 가득 차기 쉽다. 이것이 바로 일반적인 귀속 함수가 직면하기 쉬운 큰 문제이다.
한편, 꼬리 귀속은 일부 언어의 실현에 있어 상술한 문제를 피할 수 있다. 주의해야 할 것은 일부 언어에서 꼬리 귀속 자체는 함수 호출 창고가 너무 긴 문제를 없앨 수 없다. 그러면 꼬리 귀속이 무엇입니까?위에서 쓴 일반 귀속 함수func()에서 볼 수 있듯이func(n)는func(n-1)에 의존하고,func(n)는func(n-1)의 결과를 얻어야만 자신의 귀환 값을 계산할 수 있기 때문에 이론적으로func(n-1)가 귀환하기 전에func(n)는 귀환을 끝낼 수 없다.따라서func(n)는 창고에 있는 데이터를func(n-1)가 먼저 돌아올 때까지 보존해야 하며, 끝귀환의 실현은 컴파일러의 도움으로 이 제한을 없앨 수 있다.

//  

int tail_func(int n, int res) { if (n <= 1) return res; return tail_func(n - 1, n * res); } //  
 tail_func(10000000000, 1);

위에서 볼 수 있듯이 반환 결과를 호출된 매개 변수에 넣었다.이 작은 변화로 인해tailfunc(n,res) 예전처럼 굳이 tail을 받을 때까지 기다릴 필요 없어func(n-1, n*res)의 반환값을 계산해야만 자신의 반환 결과를 계산할 수 있습니다. 이것은 완전히tail 와 같습니다.func(n-1, n*res)의 반환 값입니다.그래서 이론상:tailfunc(n)가tail 호출 중func(n-1) 이전에는 창고에 놓인 물건을 완전히 소각할 수 있다.
이것이 바로 꼬리 귀속이 컴파일러의 도움을 받으면 창고 폭발을 완전히 피할 수 있는 이유이다. 모든 함수는 다음 함수를 호출하기 전에 현재 자신이 점용하고 있는 창고를 먼저 방출할 수 있다. 꼬리 귀속의 호출 체인에서 한 함수만 창고를 사용할 수 있기 때문에 무한히 호출할 수 있다!
꼬리 귀속 호출 창고 최적화 특성
독자들이 모두 알아차렸다고 믿습니다. 저는 컴파일러의 도움(또는 언어의 규정)에 의존하는 것을 강조해 왔습니다. 왜 이렇게 말합니까?먼저 다음 절차를 살펴보십시오.

 1 #include <stdio.h>
 2 
 3 int tail_func(int n, int res)  4 {  5      if (n <= 1) return res;  6 
 7      return tail_func(n - 1, n * res);  8 }  9 
10 
11 int main() 12 { 13     int dummy[1024*1024]; //  。
14     
15     tail_func(2048*2048, 1); 16     
17     return 1; 18 }

위의 프로그램은 컴파일 최적화를 실행한 것과 실행하지 않은 경우 컴파일 최적화를 실행한 결과가 다릅니다. 최적화를 실행하지 않으면 gcc-o tr functail.c 컴파일하고 실행하면 프로그램이 붕괴될 수 있지만 최적화되면: gcc -o tr -O2 functail.c, 위의 프로그램은 마지막에 정상적으로 운행할 수 있다. 
이 안의 원인은 바로 꼬리 귀속의 문법이 현재 함수를 다음 함수를 호출하기 전에 현재 점유하고 있는 창고를 없애는 것만 갖추고 있기 때문이다. 그러나 정말 이렇게 할 수 있는지의 여부는 컴파일러가 최종적으로 이렇게 할 수 있는지의 여부를 구체적으로 보아야 한다. 만약에 언어 차원에서 이런 꼬리 호출을 최적화해야 한다고 규정하지 않으면 컴파일러는 자신의 선택을 통해 서로 다른 실현을 할 수 있다. 이런 상황에서미귀환이 반드시 일반적인 귀환 문제를 해결할 수 있는 것은 아니다.
우리는 먼저 위의 예에서 최적화를 시작한 것과 최적화를 하지 않은 상황에서 컴파일된 어셈블리 코드가 어떤 차이가 있는지 볼 수 있다. 우선 최적화를 하지 않고 컴파일된 어셈블리tailfunc:

 1 .LFB3:
 2  pushq %rbp  3 .LCFI3:
 4  movq %rsp, %rbp  5 .LCFI4:
 6         subq    $16, %rsp  7 .LCFI5:
 8         movl    %edi, -4(%rbp)  9         movl    %esi, -8(%rbp) 10         cmpl    $1, -4(%rbp) 11         jg .L4 12         movl    -8(%rbp), %eax 13         movl    %eax, -12(%rbp) 14         jmp .L3 15 .L4:
16         movl    -8(%rbp), %eax 17  movl %eax, %esi 18         imull   -4(%rbp), %esi 19         movl    -4(%rbp), %edi 20  decl %edi 21         call tail_func 22         movl    %eax, -12(%rbp) 23 .L3:
24         movl    -12(%rbp), %eax 25         leave
26         ret

위에 적색으로 표시된 문장을 주의하세요.call지령은 바로 함수 호출을 진행합니다.이것은 먼저 창고를 압수한 다음에 jmp가tailfunc, 현재 창고는 아직 사용 중입니다!미귀착의 역할이 발휘되지 않았다는 얘기다.
다시 한 번 최적화된 어셈블리를 열어보자.

 1 tail_func:
 2 .LFB13:
 3         cmpl    $1, %edi  4         jle .L8  5         .p2align 4,,7
 6 .L9:
 7  imull %edi, %esi  8  decl %edi  9         cmpl    $1, %edi 10         jg .L9 11 .L8:
12  movl %esi, %eax 13         ret

7, 10행, 특히 10행에 주의하세요!tail_func () 에 함수 호출이 없습니다!그것은 단지 현재 함수의 두 번째 매개 변수를 고쳐서 바로 함수가 시작되는 곳으로 넘어갈 뿐이다.이곳의 실현 본질은 사실: 다음 함수 호출은 현재 함수의 창고를 계속 사용합니다!
이것이 바로 미귀환이 가져올 수 있는 효과이다. 창고의 증가를 통제하고 창고의 압축을 줄이면 프로그램 운행의 효율도 더욱 높아질 수 있다!
위에서 쓴 것은 c의 실현이다. 앞에서 말한 바와 같이 이것은 모든 언어가 지원하는 것이 아니다. 어떤 언어, 예를 들어python의 경우 뒤에 돌아가는 문법은python에 아무런 작용이 없고 터질 때도 터진다.

def func(n, res): if (n <= 1): return res return func(n-1, n*res) if __name__ =='__main__': print func(4096, 1)

python뿐만 아니라 C#도 지원하지 않는다고 합니다. 저는 인터넷에서 이 링크를 찾았습니다. https://connect.microsoft.com/VisualStudio/feedback/details/166013/c-compiler-should-optimize-tail-calls 마이크로소프트 사람들은 위에서 이 최적화를 실현하려면 몇 가지 문제를 처리해야 한다고 대답했습니다. 생각보다 쉽지 않아서 잠시 실현하지 못했습니다. 그러나 이 대답은 2007년이 되었습니다. 지금까지 세월이 변천했는데 지원되었는지 모르겠습니다.내가 보기에 조씨가 쓴 마지막 귀속 블로그는 2009년에 c#를 예로 들었는데 현재 c#는 이 최적화를 지지하고 있는 것 같다(대기).

후임용

앞의 토론은 줄곧 꼬리 귀속에 집중되었다. 이것은 사실 좀 좁다. 꼬리 귀속의 최적화는 꼬리 호출 최적화라는 큰 범주에 속한다. 이른바 꼬리 호출이라는 형식은 꼬리 귀속과 매우 비슷하다. 모두 하나의 함수 안의 마지막 동작은 다음 함수를 호출하는 것이다. 다른 것은 호출하는 사람이 누구인지 분명히 꼬리 호출은 꼬리 호출의 특례일 뿐이다.

int func1(int a)
{
   static int b = 3;
   return a + b;
}

int func2(int c)
{
    static int b = 2;

    return func1(c+b);
}

상기 예에서func2는func1을 호출하기 전에도 분명히 자신이 점유한 창고 공간을 완전히 잃어버릴 수 있다. 원인은 꼬리 귀속과 같기 때문에 이론적으로도 최적화할 수 있다. 사실상 이런 최적화는 프로그램 컴파일 최적화에서 흔히 볼 수 있는 옵션이다. 심지어 많은 언어들이 표준에서 꼬리 호출에 대한 최적화를 직접 요구한다. 원인은 뚜렷하다. 꼬리 호출은 프로그램에서 자주 나타난다.최적화는 창고 공간의 사용을 줄일 수 있을 뿐만 아니라 통상적으로 프로그램 운영 효율에도 비교적 큰 향상을 가져다 줄 수 있다.