再帰 【recursion】 リカーシブ / recursive / リカージョン / recurse

概要

再帰（recursion）とは、あるものの定義や記述に、それ自身が含まれること。そのような定義を「再帰的定義」という。

例えば、フィボナッチ数列の定義 Fn+2=Fn+1+Fn は、数列のある項を算出するのに手前の項の値を用いている。このように、自身のある段階を定義するために、自らの別の段階や状態を参照するような構造を再帰という。

再帰が成り立つためには、再帰を用いずに定義される基底段階と、最終的に基底段階にたどり着くような各段階の導出手順が必要となる。いずれかが欠けた自己言及的な定義は無限後退や循環参照を引き起こし、各段階の状態が確定できなくなる。

プログラミングの分野では、関数やメソッドなどの処理内容の記述の中に、自身の呼び出しを行なうコードが含まれることを「再帰呼び出し」（recursive call：リカーシブコール）と呼び、そのような関数を「再帰関数」（recursive function）という。

こうした構造を用いて記述されるアルゴリズムを「再帰的アルゴリズム」（recursive algorithm）という。フィボナッチ数列の列挙や階乗の計算 n!=n×（n-1）! のように定義に再帰的な構造が含まれる場合には、再帰的なプログラム構造によってシンプルに実装することができる。

また、プログラムが取り扱うデータ構造について、要素として配列を格納した配列、要素として木構造を格納した木構造など、あるデータ構造の要素としてそのデータ構造が収まっているような入れ子状の構造を「再帰的データ構造」「再帰データ型」などと呼ぶことがある。

(2024.3.12更新)

他の辞典による解説 （外部サイト）

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる