C言語 再帰関数の基本と作り方: 階乗・フィボナッチで理解

// 典型的な再帰関数の骨組み
// 1) ベースケース(必ず終了する条件)
// 2) 再帰ステップ(問題を小さくして自分自身を呼ぶ)
// 3) 小さくした結果を組み合わせて答えを返す

#include <stdio.h>

// プロトタイプ宣言(後で定義する関数を先に知らせる)
long long f(int n);

int main(void) {
    int n = 3;
    long long r = f(n);
    printf("f(%d) = %lld\n", n, r);
    return 0;
}

// 再帰関数の定義(例: 単なる雛形)
long long f(int n) {
    // ベースケース: これ以上分割しない最小のケース
    if (n <= 0) {
        return 1; // 例として1を返す
    }
    // 再帰ステップ: 問題を小さくして自分を呼ぶ
    long long smaller = f(n - 1);
    // 小さくした結果を使って答えを組み立てる
    return n * smaller;
}

#include <stdio.h>

// 呼び出し回数をカウントするフィボナッチ
long long fib_count(int n, long long *counter) {
    (*counter)++;              // 呼び出しが1回増えた
    if (n <= 1) return n;      // ベースケース
    return fib_count(n - 1, counter) + fib_count(n - 2, counter);
}

#include <stdio.h>

// プロトタイプ宣言
unsigned long long factorial(unsigned int n);
unsigned long long factorial_trace(unsigned int n, unsigned int depth);

// 実装: 通常の再帰版
unsigned long long factorial(unsigned int n) {
    if (n == 0) {
        return 1; // ベースケース
    }
    return n * factorial(n - 1); // 再帰ステップ
}

// 実装: トレース付き(学習用)
unsigned long long factorial_trace(unsigned int n, unsigned int depth) {
    // インデントを表示(深さごとに2スペース)
    for (unsigned int i = 0; i < depth; ++i) printf("  ");
    printf("enter factorial(%u)\n", n);

    if (n == 0) {
        for (unsigned int i = 0; i < depth; ++i) printf("  ");
        printf("return 1\n");
        return 1;
    }

    unsigned long long sub = factorial_trace(n - 1, depth + 1);
    unsigned long long ans = n * sub;

    for (unsigned int i = 0; i < depth; ++i) printf("  ");
    printf("return %u * factorial(%u) => %llu\n", n, n - 1, ans);

    return ans;
}

int main(void) {
    unsigned int n = 5;
    printf("n = %u のトレース:\n", n);
    unsigned long long result = factorial_trace(n, 0);
    printf("factorial(%u) = %llu\n", n, result);
    return 0;
}

// ループ版(反復)の階乗
unsigned long long factorial_iter(unsigned int n) {
    unsigned long long acc = 1;
    for (unsigned int i = 1; i <= n; ++i) {
        acc *= i;
    }
    return acc;
}

#include <stdio.h>

// 素直なフィボナッチ
long long fib(int n) {
    if (n <= 1) return n;                 // ベースケース
    return fib(n - 1) + fib(n - 2);       // 再帰ステップ
}

// 呼び出し回数を数える版(学習用)
long long fib_count(int n, long long *counter) {
    (*counter)++;                         // 呼び出し回数をカウント
    if (n <= 1) return n;
    return fib_count(n - 1, counter) + fib_count(n - 2, counter);
}

int main(void) {
    for (int i = 0; i <= 10; ++i) {
        long long calls = 0;
        long long v = fib_count(i, &calls);
        printf("n=%d, fib=%lld, calls=%lld\n", i, v, calls);
    }
    return 0;
}

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

// メモ化つきフィボナッチ
long long fib_memo(int n, long long *memo, int memo_size) {
    if (n < 0) return -1; // 簡易エラー扱い
    if (n < memo_size && memo[n] != -1) {
        return memo[n];   // 既計算の結果を再利用
    }
    long long v;
    if (n <= 1) {
        v = n;            // ベースケース
    } else {
        v = fib_memo(n - 1, memo, memo_size) + fib_memo(n - 2, memo, memo_size);
    }
    if (n < memo_size) memo[n] = v; // 配列範囲内なら保存
    return v;
}

int main(void) {
    int n = 50;
    int memo_size = n + 1;
    long long *memo = (long long *)malloc(sizeof(long long) * memo_size);
    if (!memo) return 1;
    for (int i = 0; i < memo_size; ++i) memo[i] = -1;

    long long v = fib_memo(n, memo, memo_size);
    printf("fib(%d) = %lld\n", n, v);

    free(memo);
    return 0;
}

// 反復版フィボナッチ
long long fib_iter(int n) {
    if (n <= 1) return n;
    long long a = 0, b = 1; // a=fib(0), b=fib(1)
    for (int i = 2; i <= n; ++i) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return b;
}

// 尾再帰版フィボナッチ(最適化があればループ相当)
long long fib_tail_helper(int n, long long a, long long b) {
    if (n == 0) return a;
    if (n == 1) return b;
    return fib_tail_helper(n - 1, b, a + b); // 末尾で自分を呼ぶ
}

long long fib_tail(int n) {
    return fib_tail_helper(n, 0, 1);
}

// 簡易インデント関数(学習用)
void indent(unsigned int depth) {
    for (unsigned int i = 0; i < depth; ++i) {
        printf("  "); // 2スペース
    }
}