tail recursion の使い方の詳細説明_PHP チュートリアル-PHPチュートリアル-php.cn

tail recursion の使い方の詳細説明_PHP チュートリアル

WBOY

リリース： 2016-07-21 15:10:24

オリジナル

1213 人が閲覧しました

ここ数日間、末尾再帰に関するいくつかの記事を見てきました。私はこれまで末尾再帰についてよく知らなかったので、戻って末尾再帰について勉強しました。

末尾再帰の概念
末尾再帰の概念は、再帰の概念のサブセットです。通常の再帰の場合、再帰呼び出しスタックを記憶しなければならないコストは計り知れません。たとえば、以下の PHP セクションの最初の例では、PHP を使用して階乗関数を作成しますが、これにより再帰によりスタックオーバーフローエラーが発生します。末尾再帰の目的は、再帰的なスタック消費の欠点を解消することです。

コードレベルから見ると、末尾再帰は実際に一文で明確に説明できます:

関数の最後の操作は再帰呼び出しです

たとえば、php での「フィボナッチ」数列の再帰実装:

コードをコピーしますコードは次のとおりです

fibonacci.php $n < 2) { 
 $n を返す; 再帰関数ですが、フィボナッチの最後の演算は加算演算であるため、末尾再帰ではありません。 

末尾再帰に変換します: 

コードをコピーします 

 コードは次のとおりです:

function fibonacci2($n, $acc1, $acc2) {
if ($n == 0) { return $ acc1;

}
Return fibonacci2($n-1, $acc2, $acc1 + $acc2);

fibonacci2 は、2 つのアキュムレーター acc1 と acc2 を加算して初期値を与えます。覚えておいてください: 再帰を末尾再帰に変換するというアイデアは、アキュムレータを増やし、再帰的な外部操作を減らす必要があります。末尾再帰には、さまざまな言語でさまざまな用途があります。最も一般的に使用されるのは、関数型プログラミング Erlang です。再帰的に見えるほとんどすべての関数は、末尾再帰になるように変更されます。いくつかの異なる言語での末尾再帰のパフォーマンスと応用について話しましょう。

phpでの末尾再帰

実験してみましょう

} 
 return fastial($n-1) * $n; 
} 

var_dump(factorial(100000000)); 

コードをコピーします
コードは次のとおりです。

function fastial($n, $acc){
if($n == 0) { return $acc;

} return fastial($n-1, $acc * $n) ;}

var_dump(factorial(100000000, 1));

実験結果:

PHPでは
末尾再帰には最適化効果がないことが判明しました!

C の末尾再帰

C での末尾再帰の最適化は、gcc コンパイラーによって行われます。 gcc でコンパイルするときに -O2 を追加すると末尾再帰が最適化されます

生成されたアセンブリコードを直接確認できます:

(gdb、gcc –O2 階乗を使用します。c –o 階乗を使用します。階乗を無効にします)

-O2 なしで生成されたアセンブリ:

O2 最適化を追加したアセンブリ:

あまり頭でっかちにならないでください。私も初めてアセンブリを見ていますが、このコードは非常に単純です。オンラインでコマンドを検索すれば理解できます：

コードをコピーコードは次のとおりです:

function factoral(n, sum) {
 while(n != 0){
 sum = n * sum
 n = n-1
 }
 return sum 
 
}

gcc は確かにインテリジェントな最適化を行います。

まだ興味がある場合は、-O3 を使用して末尾再帰を最適化し、アセンブリ命令を表示できます

-O3 の最適化はループを直接拡張することです

概要

一般的な線形再帰を末尾再帰に変更する最大の利点は、再帰呼び出しスタックのオーバーヘッドが削減されることです。 PHP の例から、プログラムに対する再帰オーバーヘッドの影響が明確にわかります。ただし、すべての言語が末尾再帰をサポートしているわけではありません。たとえば、上記の例の C 言語での末尾再帰の最適化は、末尾再帰をサポートしている言語でも一般にコンパイル段階で最適化されます。末尾再帰を使用してコードを最適化する場合は、まず言語による末尾再帰のサポートを理解する必要があります。