フィボナッチ数列

フィボナッチ数列について。

数列Fに関して、F(0) = 0、F(1) = 1 と定義し、以後

F(n + 2) = F(n) + F(n + 1) （n ≧ 0）

となる時、この数列をフィボナッチ数列という。

具体的には、こんな感じ。

0, 1, 1, 2, 3, 5, 8, 13, 21, ・・・

最初の要素を0番目と数えると、
6番目の要素である 8 は、4番目の要素である3と5番目の要素である5の和となっており、
8番目の要素である21は、6番目の要素である8と7番目の要素である13の和となっていることが確認できる。

さて、フィボナッチ数列ずらずらと表示するプログラムを書いてみる。

・・・

System.out.print(0 + ", " + 1);

recursive(0, 1);

・・・

void recursive(int a, int b) {
	
	int _val = a + b;
	
	System.out.print(", " + _val);
	
	recursive(b, _val);
	
	return;
}

こんな感じ。

0番目の要素0と1番目の要素1は自明で与えられるため、計算の対象にはならない。
0番目の要素と0と1番目の要素1を引数にして recursive() メソッドを呼び出す。
呼び出された recursive() メソッドは、引数を加算することで2番目の要素の計算を行い、更に1番目の要素とたった今算出した2番目の要素を引数に、自分自身を呼び出す。recursive() メソッドが入れ子状態で際限なく呼び出されていく。

このように自分自身を入れ子的に呼び出す手法を「再帰呼び出し」と呼び、フィボナッチ数列のように再帰を用いて表現できるアルゴリズムを「再帰的アルゴリズム」と呼ぶ。