PHP 再帰アルゴリズムとアプリケーションの紹介

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

1. サブルーチンを呼び出す意味:

メインプログラムがサブルーチン A を呼び出すステートメントを実行すると、システムは必要なフィールド データをいくつか保存し、BASIC 言語に似た GOTO ステートメントを実行してサブルーチン A にジャンプします (わかりやすくするために、ここではパラメーターの受け渡しプロセスは無視しています)。サブルーチン A がサブルーチン B を呼び出すステートメントを実行すると、システムは上記のように動作し、サブルーチン B にジャンプします。サブルーチン B はすべてのステートメントを実行した後、サブルーチン A に戻ってサブルーチン B の次のステートメントを呼び出します (ここでは戻り値の処理は無視しています)。サブルーチン A の実行後、メイン プログラムに戻ってサブルーチン A の次のステートメントを呼び出し、メイン プログラムを最後まで実行します。比較すると、食事の途中 (メイン プログラムを実行) に誰かが電話をかけてきました (サブルーチン A を実行)。まだ話している間に、電話が再び鳴りました (サブルーチン B を実行)。まずは電話に出て、誰かと話しを終え、最後に食事を終える必要がありました (この食事は私にとって本当に疲れます J)。

2. 再帰関数を理解する

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

お願いします！ n を入れることができます!この定義は要件 3 を意味します。 、まず 2 を見つけなければなりません。 、要件2！ 、まず 1 を見つけなければなりません。 、要件1！ 、まず 0 を見つけなければなりません。 、0!=1 なので、1!=0!*1=1 となり、2!、3! が見つかります。それぞれ関数として表現すると、除算は 0 で計算されることがわかります。サブルーチン、他のサブルーチンも基本的には同様です。次のようなサブルーチンを設計できます。

 int 階乗(int i){
整数 ;
 res =階乗(I-1)*i;
 res を返します。
 }

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

 int 階乗(int i){
整数 ;
 (I > 0)の場合res =階乗(I-1)*i; それ以外の場合res = 1 ;
 res を返します。
 }

3. PHPの再帰アルゴリズムを使用して問題を解決する方法

例: s=1+2+3+4+5+6+…+n を求めます。 以前は、この問題を解くのに循環累積法がよく使用されていました。ここで再帰的な方法を使用する場合は、次の 2 つの点を考慮する必要があります。
1) 問題が再帰的な記述に変換できるかどうか。
2) 再帰を終了するための境界条件はありますか?

明らかに、再帰の両方の条件が満たされています。

 1) s(n) = s(n-1)+n です。
 2) s(1)=1

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

 int 進行(int n){
整数 ;
 if ( n = 1 ) res = 1 else res =進行(n-1)+n;
 res を返します。
 }

4. 再帰の応用

二分木の順序走査

void inorder (BinTree T) {
もし（T）{
 inorder(T- > lchild);
 printf("%c",T- >データ);
 inorder(T- > rchild);
 }
 }