再帰とは？
再帰（さいき／recursion）とは、ある処理の中で自分自身（同じ手続き）を呼び出す解き方です。大きな問題を、ひと回り小さい同じ問題に分けて解くのがねらいです。
ポイントは、呼び出すたびに問題が小さくなり、いつかこれ以上分けられない最小のケース（ベースケース）に行き着くこと。ここが再帰の終わりの合図で、これに達すると答えを返し、呼び出しを逆順にたどって全体の答えが組み上がります。
ベースケースを書き忘れると止まりません。自分を無限に呼び続け、呼び出し情報が積み上がってスタックオーバーフローで異常終了します。再帰の裏では、戻り先を積んでいくコールスタック（LIFOのスタック）が働いています。
基本情報技術者試験では、再帰関数のトレース、階乗やフィボナッチ、ハノイの塔（最小手数 2ⁿ−1）などが定番です。「小さい同じ問題に分ける・終わりが要る・裏でスタックが動く」を押さえましょう。