【C言語】第5章第5回：再帰関数の基本と応用

再帰関数は、自分自身を呼び出す関数で、複雑な問題をシンプルに解決するための強力なツールです。この章では、基本から応用までを丁寧に解説します。

1. 再帰関数の基本

1.1 再帰関数とは？

再帰関数は、自分自身を呼び出す関数です。問題を小さな部分問題に分割して解決する際に役立ちます。

例：カウントダウンを行う再帰関数

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {
        printf("Blast off!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1); // 再帰呼び出し
}

int main() {
    countdown(5);
    return 0;
}

解説：

• countdown(5): 5から0まで順にカウントダウンを行います。
• if (n <= 0): 再帰を終了するための「停止条件」を設定しています。
• countdown(n - 1): 自分自身を呼び出し、引数を1減らします。

1.2 再帰関数の利用状況

再帰関数は、以下のような場面で使用されます：

• 階乗計算（Factorial）
• フィボナッチ数列の生成
• ハノイの塔問題
• 木構造やグラフの探索（DFSなど）

2. 再帰関数の応用例

2.1 階乗の計算

例：再帰関数を使った階乗計算

#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1; // 停止条件
    return n * factorial(n - 1); // 再帰呼び出し
}

int main() {
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));
    return 0;
}

解説：

• if (n == 0): 停止条件として、nが0になったら再帰を終了します。
• return n * factorial(n - 1): 再帰的に階乗を計算します。

2.2 フィボナッチ数列の生成

例：再帰関数を使ったフィボナッチ数列の生成

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) return n; // 停止条件
    return fibonacci(n - 1) + fibonacci(n - 2); // 再帰呼び出し
}

int main() {
    int num = 10;
    for (int i = 0; i < num; i++) {
        printf("%d ", fibonacci(i));
    }
    printf("\n");
    return 0;
}

解説：

• if (n <= 1): 0または1を直接返します。
• fibonacci(n - 1) + fibonacci(n - 2): 再帰的に前の2つの値を合計します。

3. 再帰関数を使用する際のポイント！

• 停止条件：再帰が無限ループに陥らないよう、必ず停止条件を設定する。
• 再帰の深さ：再帰の呼び出し回数が多いと、スタックオーバーフローが発生する可能性がある。
• 処理の効率：不要な再帰呼び出しを避けるために、メモ化（キャッシング）を利用する。

4. 練習問題

以下の課題に挑戦して、再帰関数の理解を深めましょう。

1. 2つの数の最大公約数を再帰関数で求めるプログラムを作成してください。
2. ハノイの塔問題を再帰関数で解くプログラムを作成してください。
3. 配列内の最大値を再帰関数で求めるプログラムを作成してください。

5. 練習問題の解答と解説

問1の解答

#include <stdio.h>

// 再帰関数で最大公約数を求める
int gcd(int a, int b) {
    if (b == 0) return a; // 停止条件
    return gcd(b, a % b); // 再帰呼び出し
}

int main() {
    int num1 = 48, num2 = 18;
    printf("GCD of %d and %d is %d\n", num1, num2, gcd(num1, num2));
    return 0;
}

解説：ユークリッドの互除法を使用して、最大公約数を再帰的に計算します。

6. まとめ

再帰関数は、問題を分割して解決する際に非常に便利です。しかし、効率や停止条件に注意することが重要です。次回は、再帰関数をさらに最適化する方法について学びます。