再帰 とは？

繰り返す構造をシンプルに書けるんだ。例えばフォルダの中にフォルダがあって、その中にもまたフォルダが…という構造を処理するとき、再帰を使うとすっきり書ける。

そう、だから「ベースケース」が必須なんだ。「ここで止める」という条件を必ず書く。例えばフィボナッチ数列なら「n が 0 か 1 なら n を返す」という終了条件を最初に書く。

再帰呼び出しは毎回スタックに積まれるんだ。深く呼び続けるとメモリが足りなくなって強制終了する。それがスタックオーバーフロー。深い再帰が必要なときは「末尾再帰最適化」という技法や、ループへの書き直しを検討する。

関数の最後の操作が再帰呼び出しだけのとき、一部の言語はスタックを積まずに同じフレームを使い回す最適化ができる。JavaScriptは仕様上サポートしているけど実装している処理系はほぼなくて、Haskellや関数型言語では当たり前に機能する。「末尾」に再帰が来るかどうかで、スタック消費がまったく変わってくるんだ。