再帰とは？自分自身を呼び出す関数

再帰とは、関数が問題のより小さなバージョンに対して自分自身を呼び出し、直接答えられる単純なベースケースに到達するまで繰り返すことで問題を解決することです。

再帰は問題をそれ自身の言葉で表現します。再帰関数は小さなベースケースを直接処理し、より大きなケースはすべて、より小さな入力に対して自分自身を呼び出すことでそのベースケースへと縮小します。ツリーやファイルシステムのように自然にネストしたデータには優雅ですが、各呼び出しはスタック領域を消費するため、限界のない再帰はスタックをオーバーフローさせ得ます。

再帰の2つの部分

正しい再帰関数はすべて、ベースケース（再帰を止めて直接の答えを返す条件）と再帰ケース（問題を縮小して自分自身を呼び出すもの）を必要とします。ベースケースを欠くか、それに向かって進行できないと、再帰は決して終わりません。

再帰が活きる場面

構造が自然にネストしているツリーやグラフの走査。
quicksortやmergesortのような分割統治アルゴリズム。
ディレクトリやDOMのような階層データの走査。
階乗やフィボナッチ数のように再帰的に定義される問題。

再帰 vs 反復

再帰的なものはすべてループで書けますし、その逆も可能です。再帰はネストした構造にはしばしばより明快ですが、呼び出しごとにスタック領域を使います。反復は一定のスタック領域を使い、非常に深い問題ではより安全ですが、いくらか可読性を犠牲にします。

スタックのコスト

各再帰呼び出しはスタックフレームをプッシュします。深い再帰は限られたコールスタックを使い尽くし、スタックオーバーフローを引き起こし得ます。一部の言語はこれを避けるために末尾呼び出しを最適化しますが、多くはそうしないため、深い再帰はリスクを伴います。

手短な例

階乗は factorial(n) = n <= 1 ? 1 : n * factorial(n - 1) です。ベースケース（n <= 1）が再帰を止め、各呼び出しがnをそれに向けて縮小します。

CIにおける再帰

再帰のバグ（ベースケースの欠落や到達不能）は、毎回同一に失敗するスタックオーバーフローとして現れるため、リトライは決して役立ちません。Latchkeyは決定論的なクラッシュと一時的なインフラ障害を区別し、後者のみをリトライすることで、本物の再帰バグが見えたままになるようにします。

重要なポイント

再帰はベースケースに達するまでより小さな入力に対して自分自身を呼び出すことで問題を解決する。
到達可能なベースケースと実際の進行が必要で、それがなければ決して終了しない。
深い再帰はスタックをオーバーフローさせ得る。それは決定論的なバグであり、flakyではない。