再帰関数の結果を乗算したときにg ++がまだ末尾再帰を最適化するのはなぜですか？

Question

彼らは、テール再帰の最適化は、呼び出しが関数からの復帰の直前である場合にのみ機能します。

long long f(long long n) { 
    return n > 0 ? f(n - 1) * n : 1; 
} 

再帰関数呼び出しがnであっ掛けされているので、最後の操作は、乗算ではなく、再帰呼び出しであることを意味：だから彼らは、Cコンパイラによって最適化されてはならないものの一例として、このコードを示しています。しかし、それがあるでも-O1レベル：あなたの最後のルールは、したがって、十分に正確である

：

recursion`f: 
    0x100000930 <+0>: pushq %rbp 
    0x100000931 <+1>: movq %rsp, %rbp 
    0x100000934 <+4>: movl $0x1, %eax 
    0x100000939 <+9>: testq %rdi, %rdi 
    0x10000093c <+12>: jle 0x10000094e    
    0x10000093e <+14>: nop  
    0x100000940 <+16>: imulq %rdi, %rax 
    0x100000944 <+20>: cmpq $0x1, %rdi 
    0x100000948 <+24>: leaq -0x1(%rdi), %rdi 
    0x10000094c <+28>: jg  0x100000940    
    0x10000094e <+30>: popq %rbp 
    0x10000094f <+31>: retq 

彼らがいることを言います。しかし、返品n * fact(n - 1)はテールポジションで操作しています！これは乗算*で、関数が返す前に の最後のものになります。いくつかの言語では、実際に が関数呼び出しとして実装されており、テールコール が最適化されている可能性があります。

ただし、ASMのリストからわかるように、乗算はまだ別の関数ではなくASM命令です。だから私は本当にアキュムレータのアプローチとの違いを見るのに苦労：

int fac_times (int n, int acc) { 
    return (n == 0) ? acc : fac_times(n - 1, acc * n); 
} 

int factorial (int n) { 
    return fac_times(n, 1); 
} 

これは

recursion`fac_times: 
    0x1000008e0 <+0>: pushq %rbp 
    0x1000008e1 <+1>: movq %rsp, %rbp 
    0x1000008e4 <+4>: testl %edi, %edi 
    0x1000008e6 <+6>: je  0x1000008f7    
    0x1000008e8 <+8>: nopl (%rax,%rax) 
    0x1000008f0 <+16>: imull %edi, %esi 
    0x1000008f3 <+19>: decl %edi 
    0x1000008f5 <+21>: jne 0x1000008f0    
    0x1000008f7 <+23>: movl %esi, %eax 
    0x1000008f9 <+25>: popq %rbp 
    0x1000008fa <+26>: retq 

を生成し、私は何かが足りないのですか？それともコンパイラだけが賢くなったのでしょうか？

int fac(int n) 
{ 
    int result = n; 
    while (--n) 
     result *= n; 
    return result; 
} 

GCCが知っているのに十分スマートです：あなたはアセンブリコードで見たよう

Answer 1

は、コンパイラは、基本的に（異なるデータ型を無視して）と等価であるループにあなたのコードを回すのに十分なスマートです元のfへの各呼び出しで必要な状態は、再帰呼び出しシーケンス全体を通じて2つの変数（nとresult）に保持できるため、スタックは不要です。それはfをfac_timesに変換し、両方をfacに変換することができます。これは、最も厳密な意味でのテールコール最適化の結果だけでなく、GCCが最適化に使用する他のヒューリスティックの負荷の1つです。

（私は、私はそれらについて十分に知っていないので、ここで使用されている特定のヒューリスティックについて詳細に多くを行くことはできません。）

Answer 2

非アキュムレータfは末尾再帰ではありません。コンパイラのオプションには、変換することによってループに変換するか、またはcall/some insns/retが含まれますが、その他の変換を行わないでjmp fは含まれません。

末尾呼び出しの最適化は、このような場合に適用されます：godboltから

int ext(int a); 
int foo(int x) { return ext(x); } 

ASM出力：

foo:         # @foo 
     jmp  ext      # TAILCALL 

末尾呼び出しの最適化は、jmpの代わりに機能を残す（または再帰的に）意味しますa ret。それ以外はではなく、テールコールの最適化です。しかし、jmpで最適化されたテイル再帰は本当にループです。

良いコンパイラは、条件分岐を可能な限りループの最後に置き、無条件分岐を削除します。 （asmでは、ループのスタイルはdo{}while()が最も自然です）。