再帰 — Project Hematite

問題によっては、全体の解が部分的な解と同じ形をしているものがある。再帰（recursion）はその形を利用する手法だ：より小さな入力で自分自身を呼び出す関数を書き、その小さな呼び出しがいつか直接答えられるほど単純なケースに到達することを信頼する。

関数が再帰的であるとは

再帰関数（recursive function）は本体の中に少なくとも 1 つの自己呼び出しを含む関数だ。各自己呼び出しは厳密に小さな問題を処理することが期待され、呼び出しの連鎖は問題が基底ケース（base case）— 別の呼び出しなしに即座に答えがわかるほど単純な入力 — まで縮小したとき終わる。

教科書的な例は階乗だ： $n! = n \times (n-1) \times \cdots \times 1$ 。再帰版は数学的な定義をそのまま反映する：

const std = @import("std");

fn factorial(n: u64) u64 {
    if (n == 0) return 1;        // 基底ケース：定義により 0! = 1
    return n * factorial(n - 1); // 再帰ケース
}

pub fn main() void {
    std.debug.print("{}\n", .{factorial(5)}); // 120
}

factorial(5) を呼び出すと 5 * factorial(4) を返す。その呼び出しは 4 * factorial(3) を返し、以下同様だ。引数が 0 に達すると基底ケースが発火し、乗算の連鎖が元の呼び出しまで巻き戻る。

再帰はコールスタックをどう使うか

再帰は魔法ではない — 普通の関数呼び出しの連続であり、コールスタックで学んだように、すべての関数呼び出しはコールスタックにフレームをプッシュする。再帰呼び出しも同様だ。

factorial(3) をステップごとに追う：

factorial(3) が呼び出される。フレームは n = 3 と main への戻りアドレスを保持する。まだ return できない — factorial(2) が必要だ。
factorial(2) が呼び出される。フレームは n = 2 を保持する。factorial(1) が必要だ。
factorial(1) が呼び出される。フレームは n = 1 を保持する。factorial(0) が必要だ。
factorial(0) が呼び出される。フレームは n = 0 を保持する。基底ケースが一致 — 即座に 1 を返す。
factorial(0) のフレームがポップされる。factorial(1) は答えを得た：1 * 1 = 1。1 を返す。
factorial(1) のフレームがポップされる。factorial(2) は 2 * 1 = 2 を計算して返す。
factorial(2) のフレームがポップされる。factorial(3) は 3 * 2 = 6 を計算して返す。

重要な洞察は、すべての中間フレームが再帰呼び出しの return を待ちながら同時にスタック上に残ることだ。factorial(n) はピーク時に n 個のフレームを保持する。

基底ケースが省略できない理由

基底ケースがなければ、再帰関数は自分自身の呼び出しを永遠に止めない。各呼び出しが新しいフレームをプッシュし、コールスタックはオペレーティングシステムがスタックオーバーフローでプログラムを終了するまで無制限に増大する。

fn countDown(n: i32) void {
    // 基底ケースがない — 永遠に実行されクラッシュする
    countDown(n - 1);
}

基底ケースはすべての再帰連鎖が最終的に到達しなければならない終了条件だ。再帰関数を書く前に 2 つの問いを自分に投げかけること：

直接答えられる最も単純な入力は何か？それが基底ケースだ。
それ以外のすべての入力が有限ステップでその基底ケースに近づくか？そうでなければ再帰は終了しないかもしれない。

2 つ目の例：スライスの合計

階乗は学習には便利だが、単一の整数しか受け取らない。スライスを操作する再帰関数を示す — 最初は再帰的な構造が明らかでない種類の問題だ：

const std = @import("std");

fn sumSlice(nums: []const i64) i64 {
    if (nums.len == 0) return 0;   // 基底ケース：空のスライスの合計は 0
    return nums[0] + sumSlice(nums[1..]); // 最初の要素を加算し、残りで再帰
}

pub fn main() void {
    const data = [_]i64{ 1, 2, 3, 4, 5 };
    std.debug.print("{}\n", .{sumSlice(&data)}); // 15
}

各再帰呼び出しはスライスの先頭から 1 要素を剥がす。スライスは呼び出しごとに 1 つ縮小するので、最終的に空になる — それが基底ケースだ。再帰は終了する。

nums[1..] は配列のコピーではなく新しいスライス（1 要素先を指すポインタ＋長さのペア）だ。データは複製されない。データへのビューだけが変わる。

再帰の深さとスタックオーバーフロー

各アクティブな再帰呼び出しがスタック上にフレームを保持するため、深い再帰関数はコールスタックの無制限な例と同様にスタックをオーバーフローさせることがある。ほとんどのシステムのスタックは数メガバイトで、各フレームは通常数十から数百バイトを使う。つまり問題が起きる前に大まかに数万フレームが限界だ。

factorial の場合、factorial(20) でさえ u64 をオーバーフローするため、実用的に危険な深さに達することはない。しかしユーザー提供の入力に対する汎用的な再帰 — ファイルシステムの走査や深くネストしたドキュメントのパースなど — では最大深さを意識しなければならない。

代わりにループを使う場合

再帰と反復は理論的には同等に強力で、どちらで実現できることはもう一方でも実現できる。実用的には問題の形に基づいて選択する。

再帰を選ぶとき：

問題が自然に自己の小さなコピーに分解される（木、グラフ、分割統治アルゴリズム）。
再帰的な構造がコードを数学的な定義に近いものにして正しさの検証を容易にする。

ループを選ぶとき：

再帰が末尾再帰（tail recursion）の場合 — 再帰呼び出しが関数の最後の処理で、戻る途中に仕事がない。ループが直接の同等物でスタックを増やさない。
最大入力サイズがスタックオーバーフローのリスクのある深さを生む可能性がある。
性能が重要でフレームの繰り返しプッシュとポップのオーバーヘッドを避けたい。

上の階乗の例は実際にはプロダクションコードではループの方が良い選択だ。再帰版は学習には明快だが、反復版は n に関わらず定数のスタック空間を使う：

fn factorialLoop(n: u64) u64 {
    var result: u64 = 1;
    var i: u64 = 2;
    while (i <= n) : (i += 1) {
        result *= i;
    }
    return result;
}

良い経験則：return myFunc(reducedInput) と書いていて再帰呼び出しの後に何もないなら、再帰をループに置き換える。戻る途中に仕事がある場合 — return n * factorial(n - 1) のように — 再帰的な構造が実際の仕事をしているのであって、ループに置き換えるには明示的にスタックを管理する必要があり、通常は割に合わない。

まとめ

再帰関数はより小さな入力で自分自身を呼び出す。すべての再帰的な定義は基底ケース（直接答える）と再帰ケース（入力を縮小して自分自身を呼び出す）からなる。
再帰呼び出しは他の関数呼び出しと同様にコールスタックを使う。各アクティブな呼び出しは return するまでフレームを保持するため、深い再帰はスタックオーバーフローを引き起こすことがある。
基底ケースはすべての可能な入力から到達可能でなければならず、すべての再帰ステップがそこに向かって前進しなければならない。
再帰を選ぶのは問題の構造が自然に自己相似の場合（木、分割統治）。ループを選ぶのは末尾再帰の場合や入力サイズが無制限になる可能性がある場合。