PHPマスター|再帰を理解する

コアポイント

• 再帰は、関数が直接または間接的に（関数呼び出しループを介して）自らを呼び出す関数を含む問題解決方法です。木やリストを繰り返したり、ほとんどのo（n log n）ソートを実行したりする場合に特に便利です。
• 再帰関数には、無限に自分自身を呼び出すのを防ぐための基本ケースまたは保護条項が必要であり、スタックオーバーフローエラーが発生します。この基本例は、特定の条件が満たされたときに、関数がさらに再帰的な呼び出しを行うのを止める条件です。
• 直接再帰と間接的な再帰の2種類の再帰があります。直接再帰とは、関数が直接呼び出すことを意味しますが、間接的な再帰は、関数が別の関数を介して間接的にそれ自体を呼び出すことを意味します。この記事は、直接の再帰に焦点を当てています。
• 再帰は強力なツールになる可能性がありますが、注意して使用する必要があります。 PHPは再帰関数を最適化しておらず、通常、反復的な対応物ほど効率的で高速ではありません。ただし、ファイルシステムの不確実な深さの検索や通過など、場合によっては再帰がより効率的になる場合があります。

前の投稿で、反復因子とそれらの使用方法について書きました。今日、私は反復的な兄弟を見たい：再帰。ただし、再帰について説明する前に、このコードを見てみましょう。

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

工場は、上記の数値よりも小さい断片がすべての陽性整数を増やしている結果です。次に、この例をこのように書き直しましょう

これら2つの関数を呼び出すと、同じ結果が得られますが、2番目の関数はそれ自体を呼び出すことで因子を計算することに注意してください。これは再帰と呼ばれます。

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

再帰とは何ですか？

再帰関数は、直接または関数呼び出しループを介して自分自身を呼び出す関数を指します。再帰は、問題の小さなバージョンを最初に解決し、その結果を使用して他の計算を追加して元の質問に対する答えを形成する問題解決方法を参照することもできます。通常、小さなバージョンを解くプロセスでは、このアプローチは、パズルの小さなバージョンなどを解決します。再帰関数を記述するには、いくつかのリターンメソッドを提供する必要があります。そうしないと、それ自体が永遠に呼び出し続けます（または、コールスタックが破裂したり、スクリプトがタイムアウトしたり、メモリがなくなるまで）。これは、保護条項または基本ケースと呼ばれます。再帰関数の最も単純な形式は次のとおりです。

再帰タイプ

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

関数が直接それ自体を呼び出す場合、それは直接再帰と呼ばれます。関数呼び出しループでの関数の最終呼び出しは、間接的な再帰と呼ばれます。間接的な再帰の次の例をチェックしてください：

上記の例は、実際には役に立たないコードであり、関数が別の関数を介して間接的にそれ自体をどのように呼び出すかを示すだけです。 a（n＆gt; 4）またはb（n＆gt; 4）を呼び出すと、別の関数呼び出しから呼び出される関数が発生します。関数はこのように間接的に自分自身を呼び出すことができることを知っておくことが重要ですが、この記事では直接の再帰のみを扱っています。

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

実用的な例

再帰の力を示すために、配列内のキーを検索して結果を返す関数を書きます。

<?php
function factorial($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    $factorial = 1; 
    while ($number > 0) {
        $factorial *= $number;
        $number--;
    }
    return $factorial;
}

<?php
function factorial_recursive($number) {
    if ($number < 0) {
        throw new InvalidArgumentException('Number cannot be less than zero');
    }
    if ($number == 0) {
        return 1;
    }
    return $number * factorial_recursive($number - 1);
}

すべてがスムーズに進んだが、アレイの2番目の層にのみ反復したため、3番目の層で「フィボナッチ」を検索すると失敗することに注意してください。不確実な深さの配列を検索する場合、これで十分ではありません。再帰関数として検索を書き換えることができます：

<?php
function my_recursive_func(args) {
    if (simplest case) {
        // 停止函数无限运行的基例/保护子句
        return simple value;
    }
    else {
        // 使用更简单的参数再次调用函数
        my_recursive_func(argsSimplified);
    }
}

再帰関数を使用して、ハードコード機能の深さがないため、深いアレイのいくつかのレイヤーを検索できます。配列内のすべての値を繰り返すまで、実行され続けます。

頭の再帰と尾の再帰

これまでのすべての例では、いわゆるヘッダー再帰を使用しています。関数がそれ自体を呼び出すと、それ自体の値を返す前に、コールの結果を待ちます。返品値で動作しないが、必要なすべての値をパラメーターとして渡す関数を記述できます。これは、テールコール（またはテール再帰）と呼ばれます。言語のランタイムが通話を最適化できる場合があるため、この方法は通常好まれます。そのため、コールスタックをブラストする危険はありませんが、PHPではそうしません。以下は、テールコールを作成するために変更された要因の例です。再帰コールの結果がさらに操作するのではなく、返されることに注意してください。

<?php
function A($num) {
    $num -= 1;
    if($num > 0) {  
        echo "A is Calling B($num)\n";
        $num = B($num);
    }
    return $num;
}

function B($num) {
    $num -= 2;
    if($num > 0) {
        echo "B is Calling A($num)\n";
        $num = A($num);
    }
    return $num;
}

$num = 4;
echo "Calling A($num)\n";
echo 'Result: ' . A($num);

一般的な提案

反復的に記述できるコードは、再帰的に記述できます。ただし、これは必ずしも簡単ではありません（賢明でさえ）。再帰は、木やリストを繰り返したり、ほとんどのo（n log n）ソートを実行したりする場合に優れています。ファイルシステムでの検索など、繰り返しの問題を分割する必要がある場合、および検索するためにサブディレクトリに行く必要がある場合、再帰は反復的な方法よりも適しています。不確実な深さを横断するとき、再帰はうまく機能します。 PHPは再帰関数を最適化しないことを忘れないでください。テールコールのためにそれらを書いたとしても、再帰関数は通常、反復的なカウンターパートよりも非効率的で遅くなりますが、上記のコード例のように仕事をより良くすることもあります。再帰は通常、機能プログラミングにおける反復の好ましい代替手段であるため、ほとんどの機能的言語は再帰関数を最適化します。 Xdebugを使用している場合は、システムの構成を必ず確認してください。デフォルトでは、100回の再帰コールを制限し、この制限を超えると、スクリプトが「最大ネスト制限に達した」エラーをスローします。この設定を変更する必要がある場合は、debug.max_nesting_level構成値を更新できます。最後に、スタックヒープと再帰の説明を読むことをお勧めします。

結論

この記事では、再帰と反復との比較に広範囲に紹介します。また、再帰関数を書く方法、それらを書く時期、そしてその理由も示しました。また、再帰を使用するときに遭遇するかもしれないいくつかの落とし穴について警告しようとしています。再帰はこのようなものであり、多くの経験豊富なプログラマーでさえ何年もそれを使用しないかもしれませんし、他の多くの人もそれを聞いたことさえありません。それは本当に強力な概念であるため残念です。この投稿を通して、あなた自身の再帰機能を書き始めるのに十分な知識をあなたに与えることができることを願っています。ただし、火を使用するのと同じように、常にこのツールを使用する必要があることを忘れないでください。

Flickr

によるアレクサンドル・デュレット・ルッツの写真 PHP（FAQ）の再帰を理解することに関する

FAQ

PHP再帰機能の基礎例は何ですか？

PHP再帰関数の基本的な例は、関数が無限にそれ自体を呼び出すことを妨げる条件です。これは、再帰機能の重要な部分です。基本ケースがなければ、再帰関数は無限にそれ自体を呼び出し、スタックオーバーフローエラーをもたらします。 PHPでは、基本的な例は通常、関数の先頭に「if」ステートメントを使用して定義されます。関数は、再帰コールを進める前にこの条件をチェックします。条件が満たされている場合、関数は値を返し、自分自身を呼び出すのを停止します。

PHPの再帰機能はどのように機能しますか？

PHPの再帰関数は、基本ケースと呼ばれる特定の条件が満たされるまで、それ自体の関数本体でそれ自体を呼び出します。再帰関数が呼び出されると、特定のタスクを実行し、それ自体を呼び出してタスクを繰り返します。このプロセスは、基本ケースが満たされ、関数が自分自身を呼び出すのを止めるまで続きます。関数が呼び出されるたびに、新しいレイヤーが呼び出しスタックに作成され、変数と関数呼び出しのアドレスを保存します。ベースケースが満たされると、関数が戻ってきて、レイヤーごとにコールスタックを回避し始めます。

再帰を使用してPHPのすべての問題を解決できますか？

再帰はPHPの強力なツールになる可能性がありますが、すべての問題を再帰を使用して解決できるわけではないか、解決する必要があるわけではありません。再帰は、ファイルディレクトリの移動やソート配列など、より小さく、より類似した問題に分類できる問題に最適です。ただし、不適切に使用すると、再帰は高いメモリ使用量とスタックオーバーフローエラーにつながる可能性があります。また、関数呼び出しのオーバーヘッドにより、通常、反復溶液よりも遅くなります。したがって、手元の問題を理解し、適切なアプローチを選択することが非常に重要です。

PHP再帰関数のスタックオーバーフローを防ぐ方法は？

再帰関数のスタックオーバーフローは、関数が最終的に到達する基礎インスタンスを慎重に定義することにより、防止できます。基本ケースは条件であり、この条件が満たされると、関数はさらに再帰的な呼び出しを停止します。基本ケースがなければ、関数は無限にそれ自体を呼び出し、スタックオーバーフローを引き起こします。また、各再帰呼び出しが、無限の再帰を避けるために機能を基本ケースに近づけることを確認することも重要です。

PHPの尾の再帰とは何ですか？

テール再帰は、特別なタイプの再帰であり、再帰コールは関数の最後の操作です。これは、以前の関数呼び出しを追跡する必要がなく、コンパイラまたはインタープリターが再帰を最適化し、スタックオーバーフローのリスクを減らすことができることを意味します。ただし、PHP自体は、尾の再帰的最適化をサポートしていません。したがって、PHPでTail Recursive関数を書くことはできますが、それらは最適化されておらず、再帰コールごとにスタックスペースを消費します。

再帰とPHPのループを比較する方法は？

再帰とループの両方を使用して、PHPで一連の指示を繰り返すことができます。ただし、それらは異なる動作をしており、異なる利点と短所を持っています。再帰は、複雑な問題を解決するための強力なツールであり、より小さく、より類似した問題に分類できます。これは、木やグラフなどのタスクを横断するのに特に役立ちます。一方、ループは、多くの場合、単純な繰り返しタスクに適しています。彼らは再帰よりも少ないメモリを使用し、スタックオーバーフローを引き起こす可能性は低いです。

再帰を使用して、PHPの配列を繰り返すことはできますか？

はい、再帰は、PHPでアレイ（特に多次元アレイ）を通過する非常に効果的な方法です。再帰関数を使用して配列内の各要素を反復することができ、要素自体が配列の場合、関数はアレイを繰り返して繰り返すことができます。このプロセスは、すべての要素にアクセスされるまで続きます。ただし、特に大きな配列の場合、再帰は反復溶液よりも遅く、より多くのメモリを使用する可能性があることを忘れないでください。

PHPの相互再帰とは何ですか？

相互再帰とは、ループで互いに呼び出される2つ以上の関数を指します。 PHPでは、これは関数aコール関数b、関数Bは関数Aを呼び出すことを意味します。これは、特定のタイプの問題を解決するための強力なツールになる可能性がありますが、単純な再帰よりも理解してデバッグすることも難しい場合があります。再帰機能と同様に、無限の再帰を防ぐために基本ケースを定義することが重要です。

PHPで再帰関数をデバッグする方法は？

PHPでの再帰関数のデバッグは、関数がそれ自体を複数回呼び出すため、困難な場合があります。ただし、使用できる戦略はいくつかあります。 1つの方法は、印刷ステートメントまたはデバッガーを使用して関数呼び出しを追跡し、各ステップの変数のステータスを表示することです。別の方法は、関数呼び出しを視覚化するために再帰ツリーを描くことです。また、基本ケースと再帰ケースを再確認して、それらが正しいことを確認することも重要です。

PHPで再帰を使用することの制限は何ですか？

再帰はPHPの強力なツールになる可能性がありますが、いくつかの制限があります。主な制限の1つは、再帰が深すぎる場合、スタックオーバーフローのリスクがあることです。これは、各再帰通話がコールスタックに新しいレイヤーを追加し、スタックサイズが制限されているためです。関数呼び出しのオーバーヘッドにより、再帰は反復溶液よりも遅く、より多くのメモリを使用する場合があります。さらに、再帰機能は、反復的なソリューションよりも理解してデバッグするのが難しい場合があります。

以上がPHPマスター|再帰を理解するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。