PHP - 再帰関数

こんにちは、志を抱くプログラマーたち！今日は、PHPにおける再帰関数の興味深い世界に飛び込みます。プログラミングが新しいものであるとしても、心配しないでください。私はこの概念をステップバイステップでガイドし、これまでに数多くの学生に教えてきました。で、コーヒー（またはあなたのお気に入りの飲み物）を飲みながら、このエキサイティングな旅に出発しましょう！

PHP - Recursive Functions

再帰関数とは？

具体的な内容に入る前に、まず再帰関数とは何かを理解しましょう。あなたが鏡を見て、その背後にも別の鏡があると想像してください。無限に自分自身の反射が見えますよね？それがプログラミングにおける再帰関数の動作に少し似ています！

再帰関数とは、その実行中に自分自身を呼び出す関数です。ロシアのナestingドールのデジタル版のようなものです。それぞれのドールの中に、より小さな自分自身が入っています。

再帰関数を使う理由

「なぜ関数が自分自身を呼ぶ必要があるの？それは混乱するし」と思うかもしれません。しかし、再帰関数は繰り返し構造を持つ問題を解くのに非常に便利です。特定の種類の問題において、コードをより洗練されたものにし、理解しやすくすることができます。

簡単な例を見てみましょう：

function countDown($n) {
if ($n <= 0) {
echo "Blastoff!";
} else {
echo $n . "... ";
countDown($n - 1);
}
}

countDown(5);

この関数を countDown(5) で実行すると、以下のことが起こります：

「5... 」と表示します。
それから自分自身を4で呼び出します。
「4... 」と表示します。
それから自分自身を3で呼び出します。
そして0に達するまで続けます。
最後に「Blastoff!」と表示します。

出力は以下のようになります：「5... 4... 3... 2... 1... Blastoff!」

再帰関数の構造

すべての再帰関数には、以下の2つの主要な部分があります：

基底ケース: これは再帰を止める条件です。これがなければ、あなたの関数は永遠に自分自身を呼び出し続ける（またはコンピュータがメモリを使い尽すまで）ことになります！
再帰ケース: これは関数が自分自身を呼び出す部分で、通常はパラメータが変更されています。

私たちのカウントダウン例では、if ($n <= 0) が基底ケースであり、countDown($n - 1) が再帰ケースです。

再帰を用いた階乗の計算

基本的なことを理解したところで、典型的な問題に取り組んでみましょう：階乗の計算。数nの階乗（n!と表記される）は、n以下のすべての正の整数の積です。

例えば： 5! = 5 4 3 2 1 = 120

以下に、再帰を用いて階乗を計算する方法を示します：

function factorial($n) {
if ($n <= 1) {
return 1;
} else {
return $n * factorial($n - 1);
}
}

echo factorial(5); // 出力: 120

これを分解すると：

私たちの基底ケースは if ($n <= 1) です。1!と0!はどちらも1に等しいため、この場合に1を返します。
他の数の場合、$nを(n-1)の階乗に乗じます。

私たちが factorial(5) を呼び出すと、以下のことがバックグラウンドで起こります：

factorial(5) = 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120

関数が基底ケースに達するまで自分自身を呼び出し続け、そして結果が泡のように湧き上がるのを見て、美しいと思いませんか？

再帰を用いた二分探索

次に、より複雑な例を見てみましょう：二分探索。二分探索は、ソートされたアイテムのリストからアイテムを効率的に検索するアルゴリズムです。これは、リストの可能な場所を1つに絞り込むまで、繰り返しでリストを半分に分割します。

以下に、再帰を用いた二分探索の実装を示します：

function binarySearch($arr, $left, $right, $x) {
if ($right >= $left) {
$mid = $left + floor(($right - $left) / 2);

// 要素が中央に存在する場合
if ($arr[$mid] == $x) {
return $mid;
}

// 要素が中央よりも小さい場合、左のサブ配列に存在する可能性があります
if ($arr[$mid] > $x) {
return binarySearch($arr, $left, $mid - 1, $x);
}

// それ以外の場合、要素は右のサブ配列に存在する可能性があります
return binarySearch($arr, $mid + 1, $right, $x);
}

// 要素が配列に存在しない場合
return -1;
}

$arr = [2, 3, 4, 10, 40];
$x = 10;
$result = binarySearch($arr, 0, count($arr) - 1, $x);
echo ($result == -1) ? "要素は配列に存在しません" : "要素はインデックス " . $result . " に存在します";

この関数は初めて見ると少し脅かされるかもしれませんが、分解すると以下のようになります：

我们开始检查右索引是否大于或等于左索引。这是我们继续执行的条件。
我们计算中间索引。
如果中间元素是我们的目标，我们就完成了！
如果中间元素大于我们的目标，我们递归地在数组的左半部分进行搜索。
如果中间元素小于我们的目标，我们递归地在数组的右半部分进行搜索。
如果我们已经完成了搜索（右 < 左），我们返回-1以表示找不到该元素。

这种递归方法的美丽之处在于，它自然地将问题划分为更小的子问题，一旦掌握了概念，代码就会变得优雅且易于理解。

終章

再帰関数は初めて見ると少し頭が回らないかもしれませんが、プログラマーのツールボックスにおける非常に強力なツールです。再帰関数を使うことで、複雑な問題を洗練された、簡潔なコードで解決できます。もっと練習を積むことで、再帰的解決策に適した問題を認識できるようになります。

ただし、再帰は慎重に使うべきです。時には、反復的な解決策の方が効率的で理解しやすいかもしれません。経験を積むことで、再帰を使うべき時と他のアプローチを使うべき時を見極める直感が養われます。

codingを続け、実験を続け、そして最も重要な的是、楽しみましょう！プログラミングは芸術であり科学であり、再帰のような概念をマスターすることで、美しく効率的なコードを創造できるようになります。次回まで、ハッピーコーディング！

Credits: Image by storyset