再帰とは
再帰（さいき）とは、ある関数や処理の中で、自分自身を呼び出すプログラミングの技法のことです。「再帰呼出し」とも呼ばれます。複雑な問題を、より小さな同じ形の問題に分割して解決したいときに非常によく使われます。再帰を使うことで、複雑な繰り返し処理をシンプルで読みやすいコードとして記述することができます。ただし、自分自身を呼び出す処理が無限に続かないよう、処理を終了するための「ベースケース（終了条件）」を必ず記述しなければなりません。これがないと、プログラムが無限ループに陥り、パソコンのメモリを使い果たして強制終了してしまいます。
具体例
フォルダの探索や、数学の「階乗（かいじょう）」の計算が代表的です。階乗とは、5から1までの数をすべて掛け合わせる計算です。プログラミングの例として、再帰を使って階乗を求める処理は以下のようになります。
function factorial(n) {
if (n === 1) {
return 1; // 終了条件：1のときは1を返す
}
return n * factorial(n - 1); // 自分自身を呼び出す
}
console.log(factorial(5)); // 結果は 120 (5 * 4 * 3 * 2 * 1)
もう少し詳しく
再帰の背後には、「スタック」と呼ばれるデータ構造が深く関わっています。関数が自分自身を呼び出すたびに、現在の実行状態（変数の値や次に実行するべき場所など）がコンピュータのメモリ上のスタック領域に保存されます。ベースケース（終了条件）に達して関数が値を返し始めると、スタックに積まれた実行状態が逆順に取り出され、計算が次々と完了していきます。このようにスタックを活用することで、複雑な状態管理をプログラム側ではなくシステム側に任せることができるのが再帰の強力な点です。一方で、再帰が深くなりすぎると、スタック領域のメモリ上限を超えてしまう「スタックオーバーフロー」という致命的なエラーが発生するリスクがあるため、扱うデータ量には注意が必要です。近年の一部の言語では、末尾再帰最適化と呼ばれる技術によって、このスタックオーバーフローを防ぐ工夫もされています。
試験でのポイント
基本情報技術者試験などのIT国家試験では、再帰の仕組みを理解しているかが問われる問題が頻出します。特に、再帰関数がどのように実行され、どのような値を返すかをトレース（追跡）させる問題がよく出題されます。問題を解く際の最大のポイントは、ベースケース（終了条件）は何か、関数がどのタイミングで呼び出され、引数がどのように変化していくかを図や表に書き出して整理することです。また、再帰関数と通常のループ処理（for文やwhile文など）の書き換えに関する問題も出題されることがあります。計算途中の値がメモリにどのように保持されるか、処理の順序（呼び出し順と戻る順が逆になること）をしっかりイメージできるようにしておくことが試験対策として非常に重要です。
関連する用語
再帰の概念を深く理解する上で、計算の実行状態を管理するデータ構造であるスタックや、関数の呼び出し関係を図示した木構造、さらに問題を小さく分割して解くアルゴリズム設計手法である分割統治法などもあわせて学習すると良いでしょう。