EnglishEnglish العربيةالعربية PortuguêsPortuguês 日本語日本語

関数の応用

再帰は向かい合った2つの鏡のようなものです——像の中に像が入り、遠くの光の点が消えるまで続きません。自分自身を呼び出す関数は、漸次的に問題を縮小するこの力で問題を解決します。

再帰の原理

再帰とは関数が自分自身を直接または間接的に呼び出すプログラミング手法です。すべての再帰には2つの要素が必要です。

  1. 再帰条件：問題をより小さな同種の部分問題に分解できる
  2. 基底ケース（停止条件）：最小の部分問題には直接の答えがあり、これ以上再帰しない
C 
int factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

factorial(4)を例に、実行過程を示します。

factorial(4)
= 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * 2 * factorial(1)
= 4 * 3 * 2 * 1
= 24
⚠️ 注意： 基底ケースのない再帰は無限に呼び出しを続け、スタックオーバーフローでクラッシュします。再帰を書く際は必ず最初に基底ケースを決めましょう。

古典的な再帰の例

階乗

nの階乗の定義：n! = n x (n-1)!、0! = 1。

C 
long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

long型の範囲には限界があり、factorial(20)はすでに64ビットの限界に近いことに注意してください。

フィボナッチ数列

フィボナッチの定義：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)。

C 
long fib(int n) {
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}
🔥 よくある間違い： 素朴な再帰フィボナッチは極めて非効率です！多くの部分問題が再計算されるため、fib(40)は数億回の呼び出しを要します。実践ではループやメモ化を使ってください。

ハノイの塔

n枚の円盤を棒Aから棒Cに移動します。棒Bを補助に使います。ルール：大きい円盤を小さい円盤の上に置いてはいけません。

C 
#include <stdio.h>

void hanoi(int n, char from, char mid, char to) {
    if (n == 1) {
        printf("%c -> %c\n", from, to);
        return;
    }
    hanoi(n - 1, from, to, mid);
    printf("%c -> %c\n", from, to);
    hanoi(n - 1, mid, from, to);
}

int main(void) {
    hanoi(3, 'A', 'B', 'C');
    return 0;
}
TEXT 
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

考え方：まず上のn-1枚を補助棒に移し、最大の円盤を目的棒に移し、それからn-1枚を補助棒から目的棒に移します。3枚で7手、n枚で2^n - 1手必要です。

例

再帰で整数の桁の合計を計算します。

C 
#include <stdio.h>

int digit_sum(int n) {
    if (n < 10) return n;
    return n % 10 + digit_sum(n / 10);
}

int main(void) {
    printf("%d\n", digit_sum(12345));
    printf("%d\n", digit_sum(7));
    return 0;
}
▶ 試してみよう
TEXT 
15
7

digit_sum(12345) = 5 + digit_sum(1234) = 5 + 4 + digit_sum(123) = ... = 5+4+3+2+1 = 15。

変数のスコープ

スコープは、どのコード領域が変数を認識し使えるかを決定します。

ブロックスコープ

{}内で定義された変数はそのブロック内でのみ可視であり、ブロック終了時に破棄されます。

C 
int main(void) {
    int x = 10;
    {
        int y = 20;
        printf("%d %d\n", x, y);
    }
    printf("%d\n", x);
    return 0;
}

yは内側のブロック内にしか存在せず、外側のブロックからはアクセスできません。

ファイルスコープ

すべての関数の外で定義された変数はファイルスコープを持ち、定義位置からファイル末尾まで可視です。これらは大域変数と呼ばれます。

C 
int count = 0;

void increment(void) {
    count++;
}

int main(void) {
    increment();
    increment();
    printf("%d\n", count);
    return 0;
}
⚠️ 注意： 大域変数は便利ですが、任意の関数から誤って変更される可能性があり、デバッグが難しくなります。大域変数ではなく局所変数を使うようにしてください。

名前の隠蔽

内側のスコープの変数は、外側のスコープの同名の変数を隠します。

C 
int x = 100;

int main(void) {
    int x = 10;
    printf("%d\n", x);
    return 0;
}

出力は10です。内側のxが大域のxを隠しています。内側のブロックから大域のxには直接アクセスできません。

記憶クラス

記憶クラスは変数の寿命と可視性を決定します。Cには4つの記憶クラスキーワードがあります。auto、static、extern、registerです。

auto

autoは局所変数のデフォルトの記憶クラスで、通常は省略されます。変数はブロックに入った時に作成され、ブロックを抜けると破棄されます。

C 
void func(void) {
    auto int x = 10;
}

これはint x = 10;と等価です。

static

staticが局所変数に修飾されると、変数はプログラム実行中ずっと存在しますが、スコープは関数内に限定されたままです。重要な性質：1回だけ初期化され、以降の呼び出しでは前回の値が保持されます。

C 
#include <stdio.h>

void counter(void) {
    static int count = 0;
    count++;
    printf("Call #%d\n", count);
}

int main(void) {
    counter();
    counter();
    counter();
    return 0;
}
TEXT 
Call #1
Call #2
Call #3

staticがなければ、countは毎回0に再初期化され、常に"Call #1"と出力されてしまいます。

staticが大域変数や関数に修飾されると、可視性を現在のファイルに制限します（内部結合）。他のソースファイルからexternでアクセスできなくなります。

extern

externは別のソースファイルで定義された大域変数を宣言し、コンパイラに「この変数は存在するが、現在のファイルでは定義されていない」と伝えます。

file1.c：

C 
int shared_data = 42;

file2.c：

C 
#include <stdio.h>

extern int shared_data;

int main(void) {
    printf("%d\n", shared_data);
    return 0;
}

externはメモリを割り当てず、宣言のみです。複数ファイルのプロジェクトで大域データを共有するにはexternが必要です。

register

registerはコンパイラに変数をCPUレジスタに格納するよう提案し、高速なアクセスを狙います。

C 
void fast_loop(void) {
    register int i;
    for (i = 0; i < 1000000; i++) {
    }
}

現代のコンパイラは最適化が非常に優れており、頻繁に使う変数は自動的にレジスタに配置するため、registerのヒントはほとんど効果がありません。注意：register変数はアドレスを取得（&）できません。レジスタにはメモリアドレスがないためです。

例

ループによる反復的フィボナッチ（再帰の重複計算を回避）。

C 
#include <stdio.h>

long fib_iter(int n) {
    if (n <= 2) return 1;
    long prev = 1;
    long curr = 1;
    long next;
    int i;

    for (i = 3; i <= n; i++) {
        next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    int i;
    for (i = 1; i <= 10; i++) {
        printf("F(%d) = %ld\n", i, fib_iter(i));
    }
    return 0;
}
▶ 試してみよう
TEXT 
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

この反復版の時間計算量はO(n)であり、素朴な再帰のO(2^n)よりはるかに優れています。

❓ よくある質問

Q 再帰とループはどちらが良いですか？
A ループのほうが通常効率的です。再帰は特定の問題で直感的です。単純な場合はループを優先し、木の走査のような自然に再帰的な構造には再帰を使ってください。
Q static局所変数はメモリのどこに格納されますか？
A 静的記憶域（データセグメント）にあり、大域変数と同じ領域で、スタック上ではありません。
Q extern宣言と変数定義の違いは何ですか？
A 定義はメモリを割り当て初期化する可能性があります。extern宣言はメモリを割り当てず、変数が別の場所で定義されていることを伝えるだけです。変数は1回しか定義できませんが、宣言は複数回可能です。
Q register変数は本当に速いですか？
A 現代のコンパイラは自動的にレジスタ割り当ての最適化を行います。明示的なregisterはほぼ追加の効果がなく、このキーワードは主に歴史的な意味を持ちます。

📖 まとめ

📝 練習問題

  1. 正の整数の桁を逆順に出力する再帰関数void print_reverse(int n)を書いてください（例：123は3 2 1と出力）。
  2. static変数を使って、関数が何回呼び出されたかを数える関数を書いてください。mainで5回呼び出し、回数を出力してください。
  3. 再帰で二分探索を実装してください。ソート済み配列で目標値を探し、見つかれば添字を、見つからなければ-1を返します。
100%