[C言語のはじめ方] Part10: 再帰関数の基礎

こんにちは！C言語の学習、順調に進んでいますか？ 😊 今回は、Step 2 の最後の項目「再帰関数の基礎」について学んでいきましょう。再帰関数は、一見すると少し難しく感じるかもしれませんが、基本的な考え方を理解すれば、複雑な問題をシンプルに解決できる強力なツールになります。

今回の記事では、再帰関数とは何か、どのように動作するのか、そしてどんな時に使うと便利なのかを、初心者の方にも分かりやすく解説していきます。具体的なコード例を交えながら、一歩ずつ理解を深めていきましょう！💪

再帰関数とは？

再帰関数 (Recursive Function) とは、自分自身の処理の中で、自分自身を呼び出す関数のことです。[3, 5, 6, 10, 13, 15, 25, 27, 35] 関数が自分自身を呼び出すことを「再帰呼び出し (Recursive Call)」と言います。[5, 15, 27, 35]

「え？関数が自分自身を呼ぶってどういうこと？」と思うかもしれませんね。例えるなら、合わせ鏡の中に自分が無限に映っているようなイメージ、あるいは、玉ねぎの皮をむいていくと、また同じ形の小さな玉ねぎが現れるようなイメージです🧅。

再帰関数は、大きな問題を、同じ構造を持つより小さな問題に分解して解決していくアプローチでよく使われます。[1, 2, 4, 6, 15] 数学的な問題を解いたり、木構造のような複雑なデータ構造を扱ったりする際に特に役立ちます。[1, 2, 10, 14, 31, 33]

再帰関数の基本構造

再帰関数を正しく動作させるためには、2つの重要な要素が必要です。[2, 3, 5, 13, 16, 33, 34]

1. ベースケース (Base Case): 再帰呼び出しを停止させる条件です。[2, 3, 5, 9, 15, 16, 20, 29, 33, 34] これがないと、関数は無限に自分自身を呼び出し続け、最終的にはプログラムが停止してしまいます（後述するスタックオーバーフロー）。ベースケースは、再帰の「ゴール」や「折り返し地点」のようなものです。
2. 再帰ステップ (Recursive Step): 関数が自分自身を呼び出す部分です。[2, 5, 16] ここで、問題をより小さな、同じ構造の問題へと分解していきます。呼び出すたびに、問題が少しずつ簡単になり、最終的にベースケースにたどり着くように設計する必要があります。[5, 13]

この2つの要素を組み合わせることで、再帰関数は複雑な処理を段階的に解決していきます。

例題: 階乗 (Factorial) の計算

再帰関数の最も有名な例の一つが、階乗 (Factorial) の計算です。[1, 3, 5, 6, 10, 16, 20, 22, 25, 27, 28, 29, 34] 階乗は、ある正の整数 n に対して、1からnまでのすべての整数を掛け合わせたものです。記号「!」を使って表されます。[20, 22, 27]

例:

• 3! = 3 * 2 * 1 = 6 [6, 27]
• 5! = 5 * 4 * 3 * 2 * 1 = 120 [3, 20]
• 0! は特別に 1 と定義されています。[5, 27]

階乗の定義をよく見ると、再帰的な構造が見えてきます。

• n = 0 のとき: n! = 1 (これがベースケース)
• n > 0 のとき: n! = n * (n – 1)! (これが再帰ステップ) [10, 18, 27, 34]

この定義に基づいて、階乗を計算する再帰関数をC言語で書いてみましょう。

#include <stdio.h>

// 階乗を計算する再帰関数
unsigned long long factorial(int n) {
    // ベースケース: nが0または1の場合、1を返す
    if (n == 0 || n == 1) { // [1, 3, 5, 16, 22, 29]
        return 1;
    }
    // 再帰ステップ: n * factorial(n - 1) を返す
    else { // [1, 5, 16, 22, 29]
        return (unsigned long long)n * factorial(n - 1);
    }
}

int main() {
    int num;

    printf("整数を入力してください (0以上): ");
    scanf("%d", &num);

    // 負の数が入力された場合のチェック
    if (num < 0) { // [22, 29]
        printf("負の整数の階乗は定義されていません。\n");
    } else {
        // factorial関数を呼び出して結果を表示
        unsigned long long result = factorial(num); // [3, 20]
        printf("%d の階乗は %llu です。\n", num, result); // [3, 22]
    }

    return 0;
}

再帰呼び出しの動作イメージ (factorial(3) の場合)

factorial(3) がどのように計算されるか、順を追ってみてみましょう。

1. main 関数が factorial(3) を呼び出す。
2. factorial(3): n は 3 なので、else ブロックに入る。3 * factorial(2) を計算しようとする。そのためには factorial(2) の結果が必要。
3. factorial(2): n は 2 なので、else ブロックに入る。2 * factorial(1) を計算しようとする。そのためには factorial(1) の結果が必要。
4. factorial(1): n は 1 なので、ベースケースに合致する。1 を返す。
5. factorial(2): factorial(1) から 1 が返ってきたので、2 * 1 = 2 を計算して返す。
6. factorial(3): factorial(2) から 2 が返ってきたので、3 * 2 = 6 を計算して返す。
7. main 関数は factorial(3) から 6 を受け取り、表示する。

このように、関数が次々と呼び出され（下に潜っていくイメージ）、ベースケースに到達すると、今度はその結果が呼び出し元に次々と返されていく（上に浮上してくるイメージ）ことで、最終的な答えが得られます。[13, 27]

再帰関数のメリット・デメリット

再帰関数は便利ですが、万能ではありません。メリットとデメリットを理解して使い分けることが大切です。

再帰関数を使う上での注意点

再帰関数を安全かつ効果的に使うために、以下の点に注意しましょう。

• ⚠️ 必ずベースケースを定義する: これが最も重要です！ベースケースがない、または間違っていると、無限再帰に陥り、スタックオーバーフローを引き起こします。[5, 9, 15, 16, 17, 24, 33, 34]
• ➡️ 再帰呼び出しごとに問題がベースケースに近づくようにする: 各呼び出しで、問題が少しずつ簡単になり、最終的にベースケースに到達するように設計します。[5, 13, 34] 例えば、階乗の例では n が 1 ずつ減っていくので、必ず 0 または 1 に到達します。
• 💾 スタックオーバーフローの可能性を考慮する: 再帰の深さが非常に大きくなる可能性がある場合は、ループによる実装を検討するか、他のテクニック（末尾再帰最適化など、少し高度な内容です）を考慮する必要があります。[1, 18, 30]

他の例: フィボナッチ数列

もう一つ、再帰でよく表現される例としてフィボナッチ数列 (Fibonacci Sequence) があります。[1, 2, 3, 6, 10, 25, 35] フィボナッチ数列は、最初の2項が 0 と 1 で、それ以降の項は直前の2つの項の和となる数列です。

定義:

• F(0) = 0
• F(1) = 1
• F(n) = F(n – 1) + F(n – 2) (n > 1 のとき)

これを再帰関数で実装すると以下のようになります。

#include <stdio.h>

unsigned long long fibonacci(int n) {
    // ベースケース
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    }
    // 再帰ステップ
    else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    int n;
    printf("何番目のフィボナッチ数を求めますか？ (0以上): ");
    scanf("%d", &n);

    if (n < 0) {
        printf("負の数は入力できません。\n");
    } else {
        unsigned long long result = fibonacci(n);
        printf("%d 番目のフィボナッチ数は %llu です。\n", n, result);
    }
    return 0;
}

まとめ

今回は、再帰関数の基礎について学びました。

• 再帰関数は、自分自身を呼び出す関数である。
• ベースケース（停止条件）と再帰ステップ（自分自身を呼び出す部分）から構成される。
• コードを簡潔に書けるメリットがある一方、スタックオーバーフローやパフォーマンス低下のリスクもある。
• 階乗やフィボナッチ数列、木構造の探索など、特定の種類の問題解決に適している。

再帰は、プログラミングにおける強力な思考ツールの一つです。最初は少し戸惑うかもしれませんが、例題を自分で書いて動かしてみることで、徐々に理解が深まっていくはずです。

これで Step 2 は完了です！🎉 次の Step 3 では、C言語の核心とも言える「ポインタ」について学んでいきます。難易度が上がりますが、ここを乗り越えればC言語マスターに大きく近づけます。頑張りましょう！🚀