Maximum function nesting level of '100' reached, aborting!--漫談再帰:PHPの末尾再帰とその最適化

Maximum function nesting level of '100' reached, aborting!
言語によってテール再帰のサポートが異なり、コンパイラの最適化も異なります.私たちは前にC言語の末尾再帰を見ましたが、PHPではどうでしょうか.
PHPは末尾再帰に対して最適化効果がない
まず実験を見てみましょう.01 02 function   factorial( $n ) 03 { 04      if ( $n   == 0) { 05          return   1; 06      }   07      return   factorial( $n -1) *  $n ; 08 } 09     10 var_dump(factorial(100)); 11 ?>
XDebugがインストールされている場合は、次のエラーが発生する可能性があります.1 Fatal error: Maximum  function   nesting level of  '100'   reached, aborting!
これはXDebugの保護メカニズムで、max_を通じてnesting_レベルオプションを設定します.設定を外すと、プログラムは正常に動作します.
コードが正常に動作しても、パラメータを増やし続ける限り、プログラムは遅かれ早かれエラーを報告します.1 Fatal error:  Allowed memory size of … bytes exhausted
どうしてですか.簡単に言えば、再帰的にスタックオーバーフローをもたらします.従来の考え方によれば,スタックへの再帰の影響を除去し,プログラムの効率を向上させるために,テール再帰を用いて試みることができる.01 02 function   factorial( $n ,  $acc ) 03 { 04      if ( $n   == 0) { 05          return   $acc ; 06      } 07      return   factorial( $n -1,  $acc   *  $n ); 08 } 09
  10
  11 var_dump(factorial(100, 1)); 12 ?>
XDebugも同様にエラーを報告し,プログラムの実行時間に明らかな変化はなかった.1 Fatal error: Maximum  function   nesting level of  '100'   reached, aborting!
テール再帰はphpにおいて最適化効果がないことが実証された.
PHPはどのように再帰を除去します
まず、次のソースコードを見てみましょう.01 02 function   factorial( $n ,  $accumulator   = 1) { 03      if   ( $n   == 0) { 04          return   $accumulator ; 05      } 06
  07      return   function ()  use ( $n ,  $accumulator ) { 08          return   factorial( $n   - 1,  $accumulator   *  $n ); 09      }; 10 } 11
  12 function   trampoline( $callback ,  $params ) { 13      $result   = call_user_func_array( $callback ,  $params ); 14
  15      while   ( is_callable ( $result )) { 16          $result   =  $result (); 17      } 18
  19      return   $result ; 20 } 21
  22 var_dump(trampoline( 'factorial' ,  array (100))); 23
  24 ?>
XDebugでは、アラーム効率の問題はなくなりました.
trampoline()関数に気づいたか?簡単に言えば,高次関数を用いて再帰を除去することである.もっと知りたいcall_user_func_Array、この文章を参照してください:PHP関数補完:call_user_func()とcall_user_func_array()
再帰的なスタックオーバーフローの問題を回避するための他にも多くの方法があります.例えば、Pythonでは装飾器や異常でテールコールを消滅させることができ、穴が開いたような感じがします.
小結
Cにおけるテール再帰最適化はgccコンパイラによって行われる.一般的な線形再帰修正がテール再帰の最大の利点は、再帰呼び出しスタックのオーバーヘッドを低減することである.phpの例から,再帰オーバーヘッドがプログラムに及ぼす影響が明らかになった.しかし、すべての言語が末尾再帰をサポートするわけではありません.末尾再帰をサポートする言語でも、C言語の末尾再帰の最適化など、コンパイル段階で末尾再帰を最適化するのが一般的です.テール再帰を使用してコードを最適化する場合は、この言語のテール再帰のサポートを理解する必要があります.
PHPでは、コードの可読性が向上しない限り、再帰を使用する必要はありません.やむを得ない場合は、Tail CallやTrampolineなどの技術を使用して、潜在的なスタックオーバーフローの問題を回避することを考慮したほうがいい.