実行できるCドキュメント: 再帰

Q: C言語の再帰とは何ですか？

同じ問題のより小さい版を解くために、関数が自分自身を呼ぶことです。どの再帰関数にも2つのものが必要です。再帰せずに返るベースケースと、そこへ目に見えて近づく再帰ケースです。ベースケースがなければ呼び出しは止まらず、プログラムはスタックオーバーフローでクラッシュします。

Q: C言語で階乗の関数はどう書きますか？

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); } です。ベースケースが 0 と 1 を扱い、再帰呼び出しのたびに n が1ずつ減ってそこへ到達します。int は 13! でオーバーフローするので、大きな値には unsigned long long を使ってください。

Q: なぜC言語の再帰版フィボナッチはそんなに遅いのですか？

fib(n) が fib(n-1) と fib(n-2) を呼び、同じ部分問題を何度も計算し直すからです。呼び出し回数は指数的に増えるので、fib(50) は何年もかかります。直前の2つの値を保持するループに書き換えれば線形になり、一瞬で終わります。

Q: C言語の再帰でスタックオーバーフローが起きる原因は？

呼び出しごとに引数とローカル変数のためのスタックメモリのフレームが必要で、スタックは数メガバイトしかありません。ベースケースが欠けているか到達しなければ無限再帰となり即座にクラッシュします。正しい再帰でも、数十万レベルの深さになればスタックを使い切ることがあります。

自分自身を呼ぶ関数

C言語の関数が自分自身を呼ぶことを妨げるものは何もありません。本体の中では自分の名前がスコープにあるので、これは合法です。

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* 自分自身を呼ぶ - しかし止まらない！ */
}

そしてこれは壊れています。負の数へと永久に表示し続け、やがてプログラムはクラッシュします。欠けているのはベースケース、すなわち自分自身を呼ばずに返る条件です。

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* ベースケース: 止まる */
        printf("発射！\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* 再帰ケース: より小さい問題 */
}

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

どの再帰関数にも、ちょうどこの2つの部分があります。

ベースケース - 最小の入力で、これ以上呼び出さずに直接答えるもの。
再帰ケース - 問題を厳密により小さい自分自身の版で表して解くもの。

「厳密により小さい」の部分をよく間違えます。countdown(n - 1) は呼び出しのたびに 0 へ近づきます。countdown(n) はそうではなく、n がずっと 1 になり得るなら countdown(n / 2) もそうではありません。すべての経路で問題が縮まなければ、ベースケースには決して到達しません。

階乗

定番の最初の例です。n! は n × (n-1) × ... × 1 で、0! は 1 と定義されます。この定義はすでに再帰的です。n! = n × (n-1)! なのですから。

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* ベースケース: 0! も 1! も 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* 再帰ケース */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

答えがどう組み立てられるかを見るために factorial(4) を追ってみましょう。呼び出しは下りていき、掛け算は戻りながら行われます。

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (ベースケース)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

ベースケースが返るまで、何ひとつ掛けられません。保留中のすべての呼び出しが、それぞれ自分の n を抱えたまま待っています。身につけるべきはこの点です。待っている呼び出しはメモリを占有するのです。

戻り値の型に注目してください。int は 13! あたりでオーバーフローし、静かに間違った数を返します - Cは検査しません。unsigned long long なら 20! までは届きますが、それ以上は無理です。21! は64ビットを超えるからです。ここでの制限要因は再帰ではなく、型です。

ベースケースが n == 1 ではなく n <= 1 なのは意図的です。factorial(0) は 1 であるべきで、<= がそれを扱います。n == 1 だと factorial(0) は -1、-2 と再帰し、決して終わりません - 「明らかに正しい」ベースケースがある入力を取りこぼしうる好例です。

フィボナッチ、そして素朴な版が罠である理由

フィボナッチはもうひとつの古典です。各数は直前の2つの和で、0 と 1 から始まります。再帰的な定義はそのまま書けます。

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld 回の呼び出し)\n", n, result, calls);
    }
    return 0;
}

呼び出し回数を見てください。fib(10) は177回、fib(35) は3000万回近くかかります。5つ進むごとに仕事量が約11倍になります。

理由は呼び出しの木に見えています。fib(5) は fib(4) と fib(3) を呼び、fib(4) は fib(3) をもう一度呼び、そのそれぞれが fib(2) をゼロから計算し直します。何も記憶されないので同じ部分問題が何度も解かれ、呼び出し回数はおおよそ 1.6ⁿ のように増えます。この方法での fib(50) は何日も走り、fib(100) は宇宙より長生きするでしょう。

ループ版は直前の2つの値を保持し、線形です。

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) は即座に返ります。教訓は「再帰は遅い」ではありません - 部分問題が重なる再帰は、答えを覚えないかぎり遅い、ということです。計算しながら結果を配列に保存すれば（メモ化）、再帰版も線形になります。

コールスタックとスタックオーバーフロー

どの関数呼び出しも、引数、ローカル変数、戻り先アドレスを置く場所を必要とします。その領域がスタックフレームで、呼び出しの開始時に積まれ、戻るときに降ろされます。再帰はフレームを次々と積み上げます - factorial(1000) は1000個のフレームが同時に生きていて、それぞれが自分の n を持ちます。

スタックは大きくありません。典型的な既定値は 1〜8 MB なので、現実的な上限は数万フレーム程度、各フレームが大きなローカル配列を持てばもっと少なくなります。それを超えるとプログラムは死にます。

Segmentation fault (core dumped)

これがスタックオーバーフローで、これに至る道は2つあります。

無限再帰 - ベースケースが欠けているか到達しない場合です。これはバグで、クラッシュは即座に起きます。

int bad(int n) {
    return bad(n - 1);      /* ベースケースなし - 1秒もかからずクラッシュ */
}

正しいが深すぎる - 100万要素のリストを1要素につき1回再帰する場合です。論理は正しいのですが、その方法がスタックに収まりません。ループに書き換えるか、深さが対数になるよう構造を変えましょう（二分探索やマージソートのように半分ずつ再帰すれば、100万要素でも深さは約20です）。

コンパイラによっては末尾再帰 - 再帰呼び出しが関数の最後の仕事で、その後に保留の処理がないもの - をループに変え、1つのフレームを使い回せます。上の countdown は末尾再帰ですが、factorial は違います。呼び出しが戻った後にまだ掛け算が残っているからです。しかしCはこの最適化を要求しませんので、コンパイラやフラグ次第で行われたり行われなかったりします。最適化器が末尾呼び出しを除去したからこそ動く、というCコードを書いてはいけません。

再帰が本当に勝つ場面

どの再帰関数もループに書き換えられますし、単純な数え上げならループのほうが明らかに優れています。再帰が力を発揮するのはデータ自体が再帰的なとき - 構造が自分自身の小さいコピーを含むときです。

二分探索はきれいな例です。半分を探し、次にその半分を探します。

#include <stdio.h>

/* target の添字を返す。見つからなければ -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* ベースケース: もう残っていない */
    }
    int mid = low + (high - low) / 2;       /* 大きな添字でのオーバーフローを避ける */

    if (a[mid] == target) {
        return mid;                         /* ベースケース: 見つかった */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> 添字 %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

ここではベースケースが2つあり、これは普通のことです。成功のためのものと、探索し尽くしたときのものです。深さはおよそ log₂(n) なので、10億要素でも30フレームで済みます。

再帰が自然に合う他の場面としては、木や連結リストの走査、ディレクトリの巡回、入れ子になった式の構文解析、クイックソートやマージソートのような分割統治のソートがあります。どの場合も、再帰的なコードは、それを置き換える明示的なスタック付きループより短くかつ明快です。

再帰かループか？

ループを使う       問題が線形のとき - 数える、合計する、走査する
再帰を使う         データが入れ子のとき - 木、入れ子構造、分割統治
再帰を書き換える   深さが入力サイズとともに際限なく増えうるとき
再帰は使わない     部分問題が重なるとき（メモ化しないかぎり）

実務的な注意が2つあります。再帰呼び出しはループの1周よりわずかに高くつきます - 毎回フレームを積んで降ろすからです - ので、よく実行される単純なループでは反復版が速度でもメモリでも勝ちます。そしてデバッグの様子が違います。深い再帰のスタックトレースは同じに見えるフレームが何百も並ぶので、何かが終わらないときは（上の calls カウンタのように）入り口で引数を表示しましょう。

再帰関数を書くためのチェックリスト

まずベースケースを見つける。 最小の入力は何で、その答えは何か？それを言えないなら、その関数は書けません。
再帰呼び出しは動くものと仮定する。 頭の中で追いかけないこと - factorial(n - 1) が (n-1)! を返すと信じて、それを答えに変える1ステップだけを書きましょう。
すべての経路が縮むか確認する。 どの再帰呼び出しも、0 や負数を含むあらゆる入力についてベースケースへ近づかなければなりません。
深さを確認する。 実データではおおよそ何フレームの深さになるか？数千なら問題ありませんが、数百万は無理です。
重なりを確認する。 同じ部分問題を2回計算しているなら、メモ化かループが必要です。

よくある質問

C言語の再帰とは何ですか？

同じ問題のより小さい版を解くために、関数が自分自身を呼ぶことです。どの再帰関数にも2つのものが必要です。再帰せずに返るベースケースと、そこへ目に見えて近づく再帰ケースです。ベースケースがなければ呼び出しは止まらず、プログラムはスタックオーバーフローでクラッシュします。

C言語で階乗の関数はどう書きますか？

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); } です。ベースケースが 0 と 1 を扱い、再帰呼び出しのたびに n が1ずつ減ってそこへ到達します。int は 13! でオーバーフローするので、大きな値には unsigned long long を使ってください。

なぜC言語の再帰版フィボナッチはそんなに遅いのですか？

fib(n) が fib(n-1) と fib(n-2) を呼び、同じ部分問題を何度も計算し直すからです。呼び出し回数は指数的に増えるので、fib(50) は何年もかかります。直前の2つの値を保持するループに書き換えれば線形になり、一瞬で終わります。

C言語の再帰でスタックオーバーフローが起きる原因は？

呼び出しごとに引数とローカル変数のためのスタックメモリのフレームが必要で、スタックは数メガバイトしかありません。ベースケースが欠けているか到達しなければ無限再帰となり即座にクラッシュします。正しい再帰でも、数十万レベルの深さになればスタックを使い切ることがあります。