PHP と Recursion_PHP チュートリアル-PHPチュートリアル-php.cn

PHP と Recursion_PHP チュートリアル

WBOY

リリース： 2016-07-13 17:52:19

オリジナル

1265 人が閲覧しました

プログラミングでは、再帰は非常に一般的な概念です。再帰を適切に使用すると、コードの可読性が向上しますが、いくつかの問題が発生する可能性もあります。

以下では、再帰の使用を説明するために Factorial を例として使用します。実装言語は PHP です。

関数階乗($n) {

If ($n == 0) {
return 1;
}

階乗を返します($n - 1) * $n;

}

var_dump(factorial(100));

XDebug がインストールされている場合、次のエラーが発生する可能性があります:

致命的なエラー: 関数の最大ネストレベル「100」に達したため、中止されます!

注: これは XDebug の保護メカニズムであり、max_nesting_level オプションを通じて設定できます。

たとえコードが正常に実行できたとしても、パラメータを増やし続ける限り、遅かれ早かれプログラムはエラーを報告するでしょう:

致命的なエラー: 許可されたメモリサイズ…バイトが使い果たされました

なぜですか？簡単に言うと、再帰によってスタックオーバーフローが発生します。この問題を回避するには、末尾呼び出しを使用してスタックへの再帰の影響を排除するなど、いくつかの方法を使用できます。

以下では、テールコールの意味を説明するために記述言語として Lua を使用しています。コードは次のとおりです。

関数階乗(n)

(n == 0) の場合

1 を返します
終了

階乗(n - 1) * nを返す

終わり

print(factorial(100))

このコードではスタックオーバーフローの問題も発生します。テールコールを使用してそれを行うにはどうすればよいですか?まず末尾呼び出しの定義を見てみましょう。関数呼び出しの実行後に関数が何も実行しない場合、それは末尾呼び出しと呼ばれます。比喩的に言えば、関数呼び出しを直接返すことを意味します。末尾呼び出しは元の関数を返さないため、呼び出し関数のデータを保持するために追加のスタックは必要ありません。上記のコードを末尾呼び出しに変更すると、次のコードのようになります:

階乗関数(n, アキュムレータ)

アキュムレータ = アキュムレータまたは 1

if (n == 0) then

アキュムレータを返す

終了

階乗(n - 1, アキュムレータ * n)を返す

終わり

print(factorial(100))

注: Lua での末尾呼び出しの概要については、「適切な末尾再帰」を参照してください。

猫と虎の例に従って、PHP を使用して階乗の末尾呼び出しバージョンを実装します。

関数階乗($n, $accumulator = 1) {

If ($n == 0) {

return $accumulator;
}

階乗を返す($n - 1, $accumulator * $n);

}

var_dump(factorial(100));

残念ながら、テストした結果、PHP は末尾呼び出しをまったくサポートしていないことがわかりました。幸いなことに、限界はあります。ウィキペディアのテールコールの紹介を注意深く読むと、そこにトランポリンの概念が記載されていることがわかります。簡単に言うと、高階関数を使用して再帰を排除します。この理論的根拠に基づいて、上記の末尾呼び出しコードを次のように書き換えることができます。

関数階乗($n, $accumulator = 1) {

If ($n == 0) {

return $accumulator;

}

return function() use($n, $accumulator) {
return階乗($n - 1, $accumulator * $n);

};

}

関数トランポリン($callback, $params) {
$result = call_user_func_array($callback, $params);

while (is_callable($result)) {
$result = $result();

}

$result を返す;
}

var_dump(trampoline('factorial', array(100)));

見た目は良いですが、この記事で階乗を実装するための再帰の使用は実際にはジョークであり、これについては「コード百科事典」で具体的に説明されています。

関数階乗($n) {

$結果 = 1;

for ($i = 1; $i $result *= $i;
}

$result を返す;
}

var_dump(factorial(100));

再帰によって引き起こされるスタックオーバーフローの問題を回避する方法は他にもたくさんあります。たとえば、Python では、デコレータと例外を使用して末尾呼び出しを排除できます。これにより、人々に独特の感覚を与えることができます。

末尾呼び出し最適化デコレーター (Python レシピ)

さらに、Python で末尾呼び出しがサポートされない理由についての Python の父のブログ投稿も興味深いです:

末尾再帰の除去
テールコールの最後の言葉
さて、これを書くのはやめましょう。コードの可読性を向上させることができない限り、再帰を使用する必要はありません。どうしても必要な場合は、潜在的なスタックオーバーフローの問題を回避するために、テールコールやトランポリンなどの手法の使用を検討することをお勧めします。

著者:: ラオ・ワン