再帰とは？

再帰の意味

関数やアルゴリズムが自分自身を呼び出す仕組み。問題をより小さな同種の問題に分割して解く手法（分割統治法）と相性がよく、終了条件（ベースケース）を必ず設ける必要がある。

再帰の具体例

階乗n!を求める関数は「n! = n × (n-1)!」「0! = 1（終了条件）」という定義に従い、自分自身をn回呼び出すことで計算できる。マージソートやクイックソートも再帰を使って実装されることが多い。

再帰は試験でどう引っ掛けられる？

終了条件を設定し忘れると無限に呼び出しが続き、呼び出し履歴を積むスタック領域が枯渇してスタックオーバーフローを起こす。

再帰と関連する用語

• クイックソート・マージソート・ヒープソート
• スタックとキュー