用語集
再帰さいき
前の結果を使って次の結果を定義する考え方。 漸化式・帰納法の根底にある。
前の結果を使って次の結果を定義する考え方。 漸化式・帰納法の根底にある。
再帰（recursion）とは、「前の結果を使って次の結果を定義する」考え方のことです。
| 場面 | 再帰的な仕組み |
|---|---|
| 数列 | 漸化式（前の項から次の項を決める） |
| 証明 | 数学的帰納法（ から を導く） |
| プログラミング | 関数が自分自身を呼び出す |
数列では漸化式が、証明では数学的帰納法が再帰的な構造を持ちます。たとえばフィボナッチ数列は「前の 2 項を足す」という再帰で次々と項が決まります。プログラミングでも重要な概念で、自分自身を呼び出す関数として実装されます。
ポイント 漸化式・帰納法・再帰関数は、いずれも「1 つ前（または前のいくつか）の結果に頼って次を決める」同じ発想。数Bの数列はこの再帰的思考を学ぶ場でもある。
再帰（Recursion）は、関数が自分自身を呼び出すことで、大きな問題を小さな同じ形の問題に分けて解く手法です。
| 構成要素 | 役割 | 例（階乗の計算） |
|---|---|---|
| ベースケース | 停止条件 | 0 の階乗は 1 |
| 再帰ケース | 自分自身を呼ぶ | n の階乗 = n × (n−1) の階乗 |
たとえば「フォルダの中のフォルダを順にたどる」処理や、マージソート・クイックソート のような分割統治法、木構造の探索、動的計画法などで多用されます。停止条件を忘れると呼び出しが終わらず、スタックオーバーフロー（呼び出し履歴の領域あふれ）を起こすため注意が必要です。
試験では 「自分自身を呼び出す」点と、必ず停止条件（ベースケース）が要ること、ループで書き換えられる点が問われます。