再帰

再帰とは、 ある対象xの定義の中にxが登場するような物を言う。
→ 再帰

数学における再帰

以下のようなフィボナッチ数列の定義は再帰的な定義と言える。

• a₁ = a₂ = 1
• a_n+2 = a_n+1 + a_n

再帰的でない定義（一般解）は以下のような形になる。

• a_n = 1/√5 × [ {(1+√5)/2}ⁿ  - {(1-√5)/2}ⁿ ] 

この例から分かるように、再帰的定義を用いると、そうでない定義よりも直感的な定義をすることが可能になる場合がある。

プログラミングにおける再帰

プログラミングにおいて再帰は、関数や、データ型を定義する際に用いられる事が多い。

再帰関数

ある関数fの定義内にfの呼び出しが含まれるような関数のことを言う。関数型言語では多用される手法である。クイックソートのアルゴリズムは、再帰を用いて書くとすっきりと書くことができる。

例: nの階乗を求めるプログラム（C言語）

factの定義内にfactが登場しているので再帰的な関数の定義となっている。

int fact(int n) {
 if(n <= 1)
 return 1;
 else
 return n * fact(n-1);
}

再帰的データ型

あるデータ型Aの定義内にAを含むような型のことを言う。リストや、木は再帰的データ型の一例である。

例: 二分木構造 （OCaml）

'a treeの定義内に'a treeが登場しているので再帰的な型の定義となっている。

type 'a tree = Leef | Branch of 'a * 'a tree * 'a tree;;

再帰的解法

ハノイの塔

T1	T2	T3

再帰的な手法を使い、問題を解く手順である。有名なものにハノイの塔がある。図でn個のブロックを他の塔に移動するのだが、このとき「ブロックは三本の塔のうちどれかに置ける」「ブロックはひとつずつしか動かせない」「小さいブロックの上に大きなブロックを乗せてはならない」と言う制約条件がある。

これは再帰的に考えれば簡単である。つまり、n個（n>1）のブロックをT_xからT_yに動かしたいのならn-1個のブロックをT_xからT_(6-x-y)に動かし、n番目のブロックをT_xからT_yに動かし、n-1個のブロックを改めてT_(6-x-y)からT_yに動かすのである。n=1なら普通に１回で動かせる。

つまり、n個のブロックを動かす手順数はn>1なら「n-1個のブロックを動かす手順数*2+1回」であり、n=1なら1回の手順が必要なので一般にn個動かすには2ⁿ-1回の手順が必要になることになる。

関連項目

• プログラミング関連用語の一覧
• 関数型言語
• 関数
• 数学的帰納法