フィボナッチ数列(再帰)

2017.01.23

数学

フィボナッチ数列は、イタリアの数学者レオナルド・フィボナッチが考えた「ウサギ算」から導かれる数列です。この数列は、自然界の現象に数多く出現し、ヒマワリの種の配列にもフィボナッチ数列の法則が働いているといわれています。それでは、フィボナッチ数列とはどうのようなものかを見ていきましょう。

0  1  1  2  3  5  8  13  21  34 …

n番目のフィボナッチ数をFnで表すと、Fnは再帰的に

　　F0 = 0

　　F1 = 1

　　Fn+2 = Fn + Fn+1　(n≧0)

で定義されます。

Javaソースコード

この式をJavaの再帰を使ってプログラムしたものが以下です。

Fibonacchi2.java

ダウンロード

public class Fibonacchi2 {
	// 再帰を使ったフィボナッチ数の計算
	static int fibonacchi( int n )
	{
		// n=0で0を戻す
		if ( 0 == n )
			return 0;

		// n=1で1を戻す
		if ( 1 == n )
			return 1;

		// nが2以上でFn-1とFn-2を足す
		return fibonacchi( n - 1 ) + fibonacchi( n - 2 );
	}


	// メイン
	public static void main(String[] args) {
		int n, fn;

		// F5の計算
		n = 5;
		fn = fibonacchi( n );
		System.out.println( "F" + n + "=" + fn );

		// F10の計算
		n = 10;
		fn = fibonacchi( n );
		System.out.println( "F" + n + "=" + fn );

		// F20の計算
		n = 20;
		fn = fibonacchi( n );
		System.out.println( "F" + n + "=" + fn );
	}
}

実行結果

コンパイルソースコードが「ANSI」の場合

C:\talavax\javasample>javac -encoding sjis Fibonacchi2.java

コンパイルソースコードが「UTF-8」の場合

C:\talavax\javasample>javac Fibonacchi2.java

Fibonacchi2を実行

C:\talavax\javasample>java Fibonacchi2

n=0から10のフィボナッチ数を表示します。

出力結果

F5=5
F10=55
F20=6765

Javaのソースコード解説

ここからは、このソースコードを上から順番に解説していきます。

	static int fibonacchi( int n )

フィボナッチ数を計算するfibonacchiメソッドです。変数nに値を渡すとFnを戻します。

005
006
007

		// n=0で0を戻す
		if ( 0 == n )
			return 0;

nが0のとき、0を戻しています。

009
010
011

		// n=1で1を戻す
		if ( 1 == n )
			return 1;

nが1のとき、1を戻しています。

013
014

		// nが2以上でFn-1とFn-2を足す
		return fibonacchi( n - 1 ) + fibonacchi( n - 2 );

nが2以上のとき、fibonacchi(n-1)+fibonacchi(n-2)を呼んでいます。fibonacchiメソッドからfibonacchiメソッドを呼んでおり、これが再帰処理です。

	// メイン
	public static void main(String[] args) {
		int n, fn;

		// F5の計算
		n = 5;
		fn = fibonacchi( n );
		System.out.println( "F" + n + "=" + fn );

		// F10の計算
		n = 10;
		fn = fibonacchi( n );
		System.out.println( "F" + n + "=" + fn );

		// F20の計算
		n = 20;
		fn = fibonacchi( n );
		System.out.println( "F" + n + "=" + fn );