C言語における再帰

こんにちは、将来のプログラマーたち！今日は、プログラミングの中でも最も魅力的な概念の一つである再帰について深く掘り下げます。もしこれが脅威のように思えるなら、心配しないでください - このチュートリアルの終わりまでに、あなたたちは再帰のエキスパートになるでしょう！一緒にこのエキサイティングな旅に出発しましょう。

C - Recursion

C言語における再帰関数とは？

想象してしてみてください。あなたがミラーを見て、そしてその後ろに別のミラーがあるとします。無限に自分自身の反射が見えます。それがプログラミングにおける再帰の一部です！

再帰関数とは、実行中に自分自身を呼び出す関数です。関数が「Hey、私は助けが必要だ。誰が私を助けてくれるのか？自分だ！」と言っているようなものです。

以下に簡単な例を示します：

void countdown(int n) {
if (n == 0) {
printf("blastoff!\n");
} else {
printf("%d\n", n);
countdown(n - 1);
}
}

この関数では、countdownは毎回小さな数字で自分自身を呼び出します。ロケットのカウントダウンのように、ゼロに達するまで数え続け、そしてblastoff！

C言語で再帰を使用する理由

「再帰を使う意味は何だろう？ループを使えば十分だ」と思うかもしれません。素晴らしい質問です！再帰にはいくつかの利点があります：

特定の問題に対してコードがより読みやすく、優雅になります。
木のような構造を探索するなどの再帰的な性質を持つタスクに最適です。
複雑なループ構造と一時変数の必要性を減少させます。

しかし、再帰は常に最適な選択ではありません。メモリ使用が多く、一部の問題では遅くなることがあります。プログラミングの多くのことと同様に、適切なツールを選ぶことが重要です。

再帰を用いた階乗計算

再帰の古典的な例を見てみましょう：階乗の計算。数nの階乗（n!と記述されます）は、n以下の全ての正の整数の積です。

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

int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

これを分解すると：

nが0または1の場合、1を返します（これは基準ケースです）。
それ以外の場合、nを(n-1)の階乗に乗じます。

したがって、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

そして、5! = 120です。

再帰を用いた二分探索

二分探索は、ソートされたリスト内の要素を見つける効率的なアルゴリズムです。これは、検索区間を繰り返し半分に分割します。以下に再帰的に実装します：

int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);
}

return -1;
}

この関数は以下を行います：

中央インデックスを計算します。
中央要素が目標である場合、終了します。
目標が中央要素よりも小さい場合、左半分を探索します。
目標が中央要素よりも大きい場合、右半分を探索します。
要素が見つからない場合、-1を返します。

これは、残りの範囲の中央数を常に推測する「数字当てゲーム」のハイテク版のようです！

再帰を用いたフィボナッチ数列

フィボナッチ数列は、各数が前の二つの数の和である系列です。これは再帰に最適な候補です！

以下にフィボナッチ数を再帰的に生成する方法を示します：

int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

この関数は以下のように動作します：

nが0または1の場合、nを返します（これが基準ケースです）。
それ以外の場合、前の二つのフィボナッチ数を返します。

したがって、fibonacci(5)を呼び出すと以下のようになります：

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(2) = fibonacci(1) + fibonacci(0)
fibonacci(1) = 1
fibonacci(0) = 0

後退して計算すると：

fibonacci(2) = 1 + 0 = 1
fibonacci(3) = 1 + 1 = 2
fibonacci(4) = 2 + 1 = 3
fibonacci(5) = 3 + 2 = 5

したがって、5番目のフィボナッチ数は5です！

一般的な再帰メソッド

以下に、私たちが議論した一般的な再帰メソッドの表を示します：

メソッド	説明	基準ケース	再帰ケース
階乗	n!を計算	n = 0または1	n * factorial(n-1)
二分探索	ソートされた配列内の要素を探す	要素が見つかる、または配列に存在しない	左または右半分を探索
フィボナッチ	フィボナッチ数を生成	n <= 1	fibonacci(n-1) + fibonacci(n-2)

再帰を理解する鍵は、再帰呼び出しが正しく自分の仕事を完了することを信じることです。これは、自分自身にタスクを委託するのと同じです - 彼らはあなたと同じようにそれを処理するでしょう！

再帰は最初は少し頭が回らないかもしれませんが、練習を続けることで、強力なツールになるでしょう。继续的に実験し、間もなくあなたは至る所で再帰的な解決策を見つけるようになるでしょう！

ハッピーコーディング、そして、再ursionを理解するためにはまず再ursionを理解する必要があります。 ?

Credits: Image by storyset