【C言語】 再帰関数入門｜図解でわかる仕組み・例題・落とし穴

#include <stdio.h>

// 1からnまでの合計を求める再帰関数
int sum(int n) {
    // ベースケース: nが1なら、合計は1
    if (n == 1) {
        return 1;
    }

    // 再帰ステップ:
    // sum(n) = n + sum(n - 1) と定義する
    return n + sum(n - 1);
}

int main(void) {
    int n = 4;
    int result = sum(n);
    printf("1から%dまでの合計は%dです。\n", n, result);
    return 0;
}

#include <stdio.h>

// 再帰を使って階乗を計算する関数
unsigned long long factorial(unsigned int n) {
    // ベースケース: 0! は 1 と定義する
    if (n == 0) {
        return 1;
    }

    // 再帰ステップ:
    // n! = n * (n - 1)! という数学的定義をそのまま使う
    return n * factorial(n - 1);
}

int main(void) {
    unsigned int n = 5;
    unsigned long long result = factorial(n);
    printf("%u! = %llu\n", n, result);
    return 0;
}

#include <stdio.h>

// 再帰でフィボナッチ数列を求める関数(素直な実装)
unsigned long long fibonacci(unsigned int n) {
    // ベースケース: 0番目と1番目は定義通りに返す
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }

    // 再帰ステップ:
    // F(n) = F(n - 1) + F(n - 2)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(void) {
    unsigned int n = 10;
    unsigned long long result = fibonacci(n);
    printf("F(%u) = %llu\n", n, result);
    return 0;
}

#include <stdio.h>
#include <stdbool.h>

// 再帰を使った配列の線形探索
// arr: 配列
// size: 配列の要素数
// target: 探したい値
bool linear_search_recursive(const int arr[], int size, int target) {
    // ベースケース1: 要素数が0になったら見つからなかった
    if (size == 0) {
        return false;
    }

    // ベースケース2: 最後の要素がターゲットなら見つかった
    if (arr[size - 1] == target) {
        return true;
    }

    // 再帰ステップ:
    // 最後の要素を除いた(サイズを1減らした)配列を探索する
    return linear_search_recursive(arr, size - 1, target);
}

int main(void) {
    int arr[] = {3, 8, 1, 7, 2};
    int size = (int)(sizeof(arr) / sizeof(arr[0]));
    int target = 7;

    if (linear_search_recursive(arr, size, target)) {
        printf("%d は配列の中に見つかりました。\n", target);
    } else {
        printf("%d は配列の中に見つかりませんでした。\n", target);
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

// 2分木のノードを表す構造体
typedef struct Node {
    int value;              // ノードが持つ値
    struct Node *left;      // 左の子ノードへのポインタ
    struct Node *right;     // 右の子ノードへのポインタ
} Node;

// 新しいノードを生成する関数
Node* create_node(int value) {
    Node *node = (Node*)malloc(sizeof(Node));
    if (node == NULL) {
        // メモリアロケーションに失敗した場合
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 再帰で2分木のノード数を数える関数
int count_nodes(const Node *root) {
    // ベースケース: 根がNULLならノードは0個
    if (root == NULL) {
        return 0;
    }

    // 再帰ステップ:
    // 自分自身(1個) + 左部分木のノード数 + 右部分木のノード数
    int left_count = count_nodes(root->left);
    int right_count = count_nodes(root->right);
    return 1 + left_count + right_count;
}

int main(void) {
    // 簡単な木を作成する
    //        1
    //       / \
    //      2   3
    //         /
    //        4
    Node *root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->right->left = create_node(4);

    int total = count_nodes(root);
    printf("ノード数は %d 個です。\n", total);

    // 本来はfreeでメモリを解放すべき(ここではサンプルの簡略化のため割愛)
    return 0;
}

#include <stdio.h>

// バグのある再帰関数の例(無限再帰になる)
int countdown(int n) {
    // 間違ったベースケース: n == 0 のときに止めるべきだが、1としている
    if (n == 1) {
        return 1;
    }

    printf("n = %d\n", n);

    // nを増やしてしまっているので、ベースケースに近づかない
    return countdown(n + 1);
}

int main(void) {
    countdown(5); // これを実行すると、ほぼ確実にクラッシュする
    return 0;
}

#include <stdio.h>

// バグのある例: 戻り値を返さずに再帰呼び出しだけしている
int sum_bad(int n) {
    if (n == 1) {
        return 1;
    }

    // sum_bad(n - 1) を呼び出しているが、
    // その戻り値をどこにも使っていない
    sum_bad(n - 1);

    // 何も意味のない固定値を返している
    return n;
}

int main(void) {
    int result = sum_bad(4);
    printf("結果: %d\n", result);
    return 0;
}

#include <stdio.h>

// バグのある例: 引数nを変化させないため、無限再帰になる
int sum_bad2(int n) {
    if (n == 1) {
        return 1;
    }

    // sum_bad2(n) と自分と同じ引数で呼び出している
    return n + sum_bad2(n); // n - 1 にすべきところ
}

int main(void) {
    // 実行すると無限再帰となりクラッシュする
    // int result = sum_bad2(4);
    // printf("結果: %d\n", result);
    return 0;
}

#include <stdio.h>

// ループでカウントダウン
void countdown_loop(int n) {
    for (int i = n; i >= 0; --i) {
        // ここでは単に表示するだけ
        printf("loop i = %d\n", i);
    }
}

// 再帰でカウントダウン
void countdown_recursive(int n) {
    if (n < 0) {
        return;
    }
    printf("recursive n = %d\n", n);
    countdown_recursive(n - 1);
}

int main(void) {
    int n = 5;

    printf("=== ループ版 ===\n");
    countdown_loop(n);

    printf("=== 再帰版 ===\n");
    countdown_recursive(n);

    return 0;
}