再帰とは？
さいき
再帰とは、プログラミングにおいて関数が自分自身を呼び出すことで問題を解く手法で、繰り返しや木構造の探索などに広く活用されます。
再帰（Recursion）とは、プログラミングや数学において、ある定義や関数が自分自身を参照・呼び出す構造のことです。プログラミングでは「再帰関数」と呼ばれ、関数の内部から同じ関数を呼び出すことで、繰り返し処理を簡潔に記述できます。
再帰が正常に終了するためには、必ず「基底条件（ベースケース）」が必要です。これは再帰を停止させる条件で、これがなければ関数は無限に呼び出され続け、スタックオーバーフローを引き起こします。再帰の基本構造は次のとおりです。
- 基底条件：これ以上分割できない最小のケースを直接解く
- 再帰ステップ：問題をより小さな部分問題に分割し、自身を呼び出す
再帰が特に有効な場面としては以下が挙げられます。
- 階乗（n!）やフィボナッチ数列などの数学的定義
- 木構造やグラフの深さ優先探索
- マージソートやクイックソートなどの分割統治アルゴリズム
- HTMLやJSONのようなネスト構造の解析
再帰はコードを直感的に記述できる反面、深い再帰はメモリ消費が大きくなるため、末尾再帰最適化や反復処理への書き換えが必要になる場合もあります。
使い方・例文
階乗を求める関数で、factorial(n) の内部で factorial(n-1) を呼び出す実装が再帰の典型例です。ファイルシステムのフォルダを再帰的に走査する処理なども日常的な活用例です。
この用語をシェア
最終更新: