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

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

/* 階乗の基本再帰: 0! = 1, n! = n * (n - 1)! (n >= 1) */
unsigned long long fact(unsigned int n) {
    if (n == 0) {
        return 1ULL; // ベースケース
    }
    return n * fact(n - 1); // 再帰ステップ
}

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

#include <stdio.h>

/* インデント用のスペースを出力するヘルパ */
void indent(unsigned int depth) {
    for (unsigned int i = 0; i < depth; ++i) putchar(' ');
}

unsigned long long fact_trace(unsigned int n, unsigned int depth) {
    indent(depth);
    printf("enter fact(%u)\n", n);

    if (n == 0) {
        indent(depth);
        printf("base -> 1\n");
        return 1ULL;
    }

    unsigned long long sub = fact_trace(n - 1, depth + 2); // 深さ+2で見やすく
    unsigned long long res = n * sub;

    indent(depth);
    printf("return %u * %llu = %llu\n", n, sub, res);
    return res;
}

int main(void) {
    unsigned int n = 4;
    unsigned long long r = fact_trace(n, 0);
    printf("%u! = %llu\n", n, r);
    return 0;
}

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

#define FACT_MAX_N 20u

bool fact_safe(unsigned int n, unsigned long long *out) {
    if (!out) return false;
    if (n > FACT_MAX_N) return false;   // 範囲外
    // 基本再帰
    if (n == 0) { *out = 1ULL; return true; }
    unsigned long long sub;
    if (!fact_safe(n - 1, &sub)) return false;
    *out = n * sub;
    return true;
}

int main(void) {
    unsigned int tests[] = {0, 5, 20, 21};
    for (size_t i = 0; i < sizeof(tests)/sizeof(tests[0]); ++i) {
        unsigned long long r;
        if (fact_safe(tests[i], &r)) {
            printf("%u! = %llu\n", tests[i], r);
        } else {
            printf("ERROR: %u は計算範囲外です\n", tests[i]);
        }
    }
    return 0;
}

#include <stdio.h>

/* 反復で階乗を計算 */
unsigned long long fact_iter(unsigned int n) {
    unsigned long long acc = 1ULL;
    for (unsigned int i = 1; i <= n; ++i) {
        acc *= i;
    }
    return acc;
}

int main(void) {
    for (unsigned int n = 0; n <= 10; ++n) {
        printf("%2u! (rec)=%20llu, (iter)=%20llu\n", n, /* 再帰版 */ (n==0?1ULL:n*1ULL*1), /* ダミー */ fact_iter(n));
    }
    return 0;
}

#include <stdio.h>

/* 末尾再帰: accに結果を蓄積し、最後の操作が再帰呼び出し */
unsigned long long fact_tail(unsigned int n, unsigned long long acc) {
    if (n == 0) return acc;          // 末尾位置で返す
    return fact_tail(n - 1, acc * n);
}

int main(void) {
    printf("10! = %llu\n", fact_tail(10, 1ULL));
    return 0;
}

#include <stdio.h>

/* 教科書通りの再帰: とてもわかりやすいが、遅い */
unsigned long long fib(unsigned int n) {
    if (n == 0) return 0ULL; // ベースケース1
    if (n == 1) return 1ULL; // ベースケース2
    return fib(n - 1) + fib(n - 2); // 再帰ステップ
}

int main(void) {
    for (unsigned int n = 0; n <= 10; ++n) {
        printf("F(%u) = %llu\n", n, fib(n));
    }
    return 0;
}

#include <stdio.h>
#include <string.h>

#define MAX_N 93 /* unsigned long longで収まる最大のnはF(93)まで */

unsigned long long memo[MAX_N + 1];

unsigned long long fib_memo(unsigned int n) {
    if (n == 0) return 0ULL;
    if (n == 1) return 1ULL;
    if (memo[n] != 0ULL) return memo[n];    // 既計算を再利用
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

int main(void) {
    memset(memo, 0, sizeof(memo));
    for (unsigned int n = 0; n <= 50; n += 10) {
        printf("F(%u) = %llu\n", n, fib_memo(n));
    }
    return 0;
}

#include <stdio.h>

/* 反復でO(n)時間・O(1)追加メモリ */
unsigned long long fib_iter(unsigned int n) {
    if (n == 0) return 0ULL;
    if (n == 1) return 1ULL;
    unsigned long long a = 0ULL, b = 1ULL; // F(0)=0, F(1)=1
    for (unsigned int i = 2; i <= n; ++i) {
        unsigned long long next = a + b;
        a = b;
        b = next;
    }
    return b;
}

int main(void) {
    for (unsigned int n = 0; n <= 10; ++n) {
        printf("F(%u) = %llu\n", n, fib_iter(n));
    }
    return 0;
}