36. 再帰 — 自分自身を呼ぶ関数

再帰とは、関数が自分自身を呼び出して問題を解く手法です。階乗やフィボナッチ数、木構造のたどりなど、「同じ形のより小さな問題」に分解できる処理を素直に表現できます。再帰には必ず、それ以上分解しない「基底ケース(終了条件)」と、問題を小さくして自分を呼ぶ「再帰ケース」が必要です。

下の factorial では、n が 0 のときに 1 を返すのが基底ケースで、それ以外は n * factorial(n-1) と自分自身をより小さい引数で呼ぶのが再帰ケースです。基底ケースを忘れると呼び出しが終わらず、コールスタックを使い切って実行時エラー(stack overflow)になるため、終了条件は最初に書くと安全です。

Go の標準コンパイラは末尾呼び出し最適化を保証しないため、非常に深い再帰はスタックを多く消費します。とはいえ Go のゴルーチンのスタックは必要に応じて伸びるので、通常の範囲なら問題になりません。深さが極端に大きくなる場合は、ループや明示的なスタックで書き換えることも検討しましょう。