PHP 再帰アルゴリズムとアプリケーションの概要_PHP チュートリアル-PHPチュートリアル-php.cn

PHP 再帰アルゴリズムとアプリケーションの概要_PHP チュートリアル

WBOY

リリース： 2016-07-15 13:28:20

オリジナル

907 人が閲覧しました

PHP は、動的 Web ページを開発するための推奨テクノロジーです。プログラミングに役立つように、その基本的な知識を覚えておく必要があります。 PHP 再帰アルゴリズムで何が起こっているのかを見てみましょう。

1. サブルーチン呼び出しの意味:

メインプログラムがサブルーチン A を呼び出すステートメントを実行すると、システムは必要なオンサイトデータを保存し、BASIC 言語と同様の GOTO ステートメントを実行してサブルーチンにジャンプします。 A. (わかりやすくするために、ここではパラメータを渡すプロセスを無視します)。サブプログラム A がサブプログラム B を呼び出すステートメントに到達すると、システムは上記のようにサブプログラム B にジャンプします。サブプログラム B は、すべてのステートメントの実行を終了した後、サブプログラム A に戻り、サブプログラム B の次のステートメントを呼び出します (サブプログラム A の実行が終了した後、戻り値の処理を再度無視しました)。メインプログラムに戻り、サブプログラムを呼び出します。 A. ステートメントの次のステートメントでは、メインプログラムが最後まで実行されます。比較してみましょう。私が食事中 (メインプログラムの実行中)、誰かが私に電話をかけてきました (サブルーチン A の実行中)。途中でまた電話が鳴りました (サブルーチン B の実行中)。私は先に応答する必要がありました。電話を終え、誰かと話を終え、そしてついに食事を終える（私はこの食事を食べるのに疲れた）。

2. 再帰関数を理解する

私たちは皆、高校で数学的帰納法、PHP 再帰アルゴリズムを学びました。たとえば、次のとおりです。

n を見つけよう! nを入れることもできます！この定義は 3 が必要であることを意味します。、まず 2 を見つけなければなりません。、リクエスト２！、まず 1 を見つける必要があります。、リクエスト１！、まず 0 を見つける必要があります。、0!=1 なので、1!=0!*1=1 となり、2!、3! を求めます。それぞれ関数で表されると、0! の計算以外のことがわかります。サブルーチンを除いて、他のサブルーチンも基本的には同様です。

<ol class="dp-xml">
<li class="alt"><span><span>int factorial(int i){  </span></span></li>
<li class=""><span>int res;  </span></li>
<li class="alt">
<span></span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">factorial</font></span><span>(I-1)*i;  </span>
</li>
<li class=""><span>return res;  </span></li>
<li class="alt"><span>} </span></li>
</ol>

ログイン後にコピー

次に、メインプログラムステートメント s=factorial(3) が実行されると、factorial(3) が実行されます。 fastial(3) が実行されると、factorial(2) が呼び出されます。このとき、factorial(3) と fastial(2) は同じコードセグメントですが、メモリ上のデータ領域に注意してください。二人です！ Factorial(2) が実行されると、Factorial(1) が呼び出され、Factorial(1) が Factorial(0) と呼ばれます。factorial 関数が呼び出されるたびに、メモリに新しいデータ領域が追加されます。複数の関数は異なる名前を持つ複数の関数として理解できますが、この関数には問題があります。factorial(0) が実行されると、factorial(-1) が呼び出されます。。。無限ループが発生します。つまり、factorial 関数では、関数が適切なタイミングで呼び出されないようにする必要があります。つまり、呼び出しステートメント res=factorial(I-1)*i; が実行されないようにする必要があります。。したがって、関数を次のように変更する必要があります:

<ol class="dp-xml">
<li class="alt"><span><span>int factorial(int i){  </span></span></li>
<li class=""><span>int res;  </span></li>
<li class="alt">
<span>if (I</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>0) </span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">factorial</font></span><span>(I-1)*i; else </span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span>;  </span>
</li>
<li class=""><span>return res;  </span></li>
<li class="alt"><span>} </span></li>
</ol>

ログイン後にコピー

3. 問題を解決するために PHP 再帰アルゴリズムの使用を検討する方法

例: s=1+2+3+4+5+6+……+n を検索します。当初、私たちはこの問題について検討しました。一般的に使用されるループ累積手法です。ここで再帰的手法を使用する場合は、次の 2 つの点を考慮する必要があります:
1) 問題を再帰的な記述形式に変換できるかどうか。
2) 再帰の終了に境界条件があるかどうか。

明らかに再帰の両方の条件が存在します:

<ol class="dp-xml">
<li class="alt"><span><span>1） s(n) =s(n-1)+n  </span></span></li>
<li class=""><span>2） s(1)=1 </span></li>
</ol>

ログイン後にコピー

したがって、ソースプログラムは次のようになります:

<ol class="dp-xml">
<li class="alt"><span><span>int progression(int n){  </span></span></li>
<li class=""><span>int res;  </span></li>
<li class="alt">
<span>if (</span><span class="attribute"><font color="#ff0000">n</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span> )</span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span> else </span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">progression</font></span><span>(n-1)+n;  </span>
</li>
<li class=""><span>return res;  </span></li>
<li class="alt"><span>} </span></li>
</ol>

ログイン後にコピー

4. 再帰の適用

二分木の順走査

<ol class="dp-xml">
<li class="alt"><span><span>void inorder (BinTree T){  </span></span></li>
<li class=""><span>if (T){  </span></li>
<li class="alt">
<span>inorder(T-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>lchild);  </span>
</li>
<li class="">
<span>printf(“%c”,T-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>data);  </span>
</li>
<li class="alt">
<span>inorder(T-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>rchild);  </span>
</li>
<li class=""><span>}  </span></li>
<li class="alt"><span>} </span></li>
</ol>

ログイン後にコピー