PHPデータ構造に基づく再帰

この記事では主に PHP のデータ構造に基づいた再帰を紹介しますが、これは参考になるものです。今回はそれを共有します。必要な友人は参考にしてください。

再帰とは何ですか?

前に述べたように、再帰は大きな問題を小さな問題に分割する解決策です。一般に、再帰は関数自体の呼び出しと呼ばれます。このように言うと奇妙に聞こえるかもしれませんが、実際、再帰では関数はそれ自体を呼び出す必要があります。

A栗

たとえば、数学では、「階乗」という概念を誰もが知っています。たとえば、5 の階乗は 5*4*3*2*1 です。

• #5! = 5 * 4!

• 4! = 4 * 3!

• 3! = 3 * 2! ＃＃＃＃＃＃＃２！ = 2 * 1!

• 1! = 1 * 0!

#0! = 1
n の階乗を求めるルール、つまり n! = n * (n -1) !

• これは再帰を反映しています。このことから、5 の階乗を段階的に別の小さな問題に変換したことがわかります。

再帰アルゴリズムの特徴

すべての再帰呼び出しは、小さな副問題に基づいている必要があります。たとえば、5 の階乗は 5 に 4 を掛けた階乗です。

再帰には基本ケースが必要です。たとえば、階乗の基本ケースは 0 です。条件が 0 の場合、再帰は停止します。
再帰中のループ呼び出しは避けてください。そうしないと、コンピュータは最終的にスタック オーバーフロー エラーを表示します。

• function factorial(int $n): int
  {
      if ($n = 0) {
          return 1;
      }
      
      return $n * factorial($n - 1);
  }

上記のコードを見ると、階乗問題を解決するための基本条件、つまり n が 0 の場合に 1 を返すことがわかります。この条件が満たされない場合は、
• n

  に

  factorial(n)
を乗算した値が返されます。これは、再帰プロパティの最初と 3 番目の項目を満たします。各再帰呼び出しを大きな問題の小さなサブ問題に分割するため、ループ呼び出しを回避します。上記のアルゴリズムのアイデアは次のように表すことができます:

再帰と反復反復法を使用して上記の再帰コードを実装することもできます

function factorial(int $n): int
{
    $result = 1;
    
    for ($i = $n; $i > 0; $i--) {
        $result*= $n;
    }
    
    return $result;
}

問題が発生した場合反復を使用して解決するのは簡単ですが、なぜ再帰を使用するのでしょうか?

再帰は、より複雑な問題に対処するために使用されます。すべての問題が反復だけで解決できるわけではありません。再帰では関数呼び出しを使用して呼び出しスタックを管理するため、反復よりも多くの時間とメモリを使用します。さらに、反復では、各ステップで結果が得られますが、再帰では、結果が得られる前に、基本ケースの実行が終了するまで待つ必要があります。上記の例を見ると、再帰的アルゴリズムでは結果を保存するための変数や宣言がありませんが、反復的アルゴリズムでは $result を使用して返された結果を毎回保存していることがわかります。

フィボナッチ数列

数学では、フィボナッチ数列は特別な整数列です。数列内の各数値は、他の 2 つの数値の合計によって生成されます。ルールは次のとおりです。

function fibonacci($n)
{
    if ($n == 0) {
        return 0;
    }
    
    if ($n == 1) {
        return 1;
    }
    
    return fibonacci($n - 1) + fibonacci($ - 2);
}

最大公約数

再帰アルゴリズムを使用するもう 1 つの一般的な問題は、2 つの数値の最大公約数を見つけることです。

function gcd(int $a, int $b)
{
    if ($b == 0) {
        return $a;
    }
    
    return gcd($b, $a % $b);
}

再帰型

線形再帰

すべての再帰呼び出しでは、関数は自分自身を 1 回だけ呼び出します。これを線形再帰と呼びます。
二項再帰

二項再帰では、関数への各再帰呼び出しがそれ自体を 2 回呼び出します。フィボナッチ数列を解くアルゴリズムは二分再帰であり、他にも二分探索、分割統治アルゴリズム、マージソートなども二分再帰を利用します。
末尾再帰

再帰が操作を待たずに戻る場合、それは末尾再帰と呼ばれます。フィボナッチアルゴリズムでは、戻り値に前回の再帰の戻り値を乗算する必要があるため、末尾再帰ではなく、最大公約数を解くアルゴリズムは末尾再帰です。末尾再帰は線形再帰の形式です。
相互再帰

たとえば、各再帰呼び出しでは、A() は B() を呼び出し、B() は A() を呼び出します。このような再帰は相互再帰と呼ばれます。
ネストされた再帰

再帰関数がそれ自体をパラメーターとして再帰的に呼び出す場合、それはネストされた再帰と呼ばれます。一般的な例はアッカーマン関数です。以下の式を参照してください。

#最後の行を見ると、2 番目のパラメータが再帰関数そのものであることがわかります。

次のセクション

次の記事では、再帰を使用して、N レベル分類の構築、ネストされたコメントの構築、ディレクトリ ファイルの走査など、実際の開発で遭遇するいくつかの問題を解決します。

上記がこの記事の全内容です。皆様の学習に役立つことを願っています。その他の関連コンテンツについては、PHP 中国語 Web サイトに注目してください。

関連する推奨事項:

PHP でクライアントの実際の IP アドレスを取得する方法

PHP で Elasticsearch を使用する方法PHP

以上がPHPデータ構造に基づく再帰の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。