フィボナッチ数列(再帰) - 【ゆるゆるプログラミング】

2017/01/23 公開

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

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

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

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

で定義されます。

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

Fibonacchi2.java　←　クリックしてダウンロードページに移動

001:    public class Fibonacchi2 {
002:    	// 再帰を使ったフィボナッチ数の計算
003:    	static int fibonacchi( int n )
004:    	{
005:    		// n=0で0を戻す
006:    		if ( 0 == n )
007:    			return 0;
008:    
009:    		// n=1で1を戻す
010:    		if ( 1 == n )
011:    			return 1;
012:    
013:    		// nが2以上でFn-1とFn-2を足す
014:    		return fibonacchi( n - 1 ) + fibonacchi( n - 2 );
015:    	}
016:    
017:    
018:    	// メイン
019:    	public static void main(String[] args) {
020:    		int n, fn;
021:    
022:    		// F5の計算
023:    		n = 5;
024:    		fn = fibonacchi( n );
025:    		System.out.println( "F" + n + "=" + fn );
026:    
027:    		// F10の計算
028:    		n = 10;
029:    		fn = fibonacchi( n );
030:    		System.out.println( "F" + n + "=" + fn );
031:    
032:    		// F20の計算
033:    		n = 20;
034:    		fn = fibonacchi( n );
035:    		System.out.println( "F" + n + "=" + fn );
036:    	}
037:    }

Fibonacchi2を実行

C:\talavax\javasample>java Fibonacchi2

n=5、10、20のフィボナッチ数を表示します。

Fibonacchi2.javaの出力結果

F5=5
F10=55
F20=6765

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

003:    	static int fibonacchi( int n )

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

005:    		// n=0で0を戻す
006:    		if ( 0 == n )
007:    			return 0;

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

009:    		// n=1で1を戻す
010:    		if ( 1 == n )
011:    			return 1;

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

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

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

018:    	// メイン
019:    	public static void main(String[] args) {
020:    		int n, fn;
021:    
022:    		// F5の計算
023:    		n = 5;
024:    		fn = fibonacchi( n );
025:    		System.out.println( "F" + n + "=" + fn );
026:    
027:    		// F10の計算
028:    		n = 10;
029:    		fn = fibonacchi( n );
030:    		System.out.println( "F" + n + "=" + fn );
031:    
032:    		// F20の計算
033:    		n = 20;
034:    		fn = fibonacchi( n );
035:    		System.out.println( "F" + n + "=" + fn );

fibonacchiメソッドに5、10、20を渡して結果を表示しています。

■関連コンテンツ

フィボナッチ数列	フィボナッチ数列
フィボナッチ数列(配列)	フィボナッチ数列（配列）
数学関数について	数学関数について解説
黄金比	最も美しい比率
黄金角	ヒマワリの種の配置？
値のコンソール表示	print()、println()とは？
メソッド	メソッドについて解説

	ウサギ算ウサギ算について解説しています。１対のウサギが１ヶ月毎に１対のウサギを産んでいく場合に、数が月後にウサギの対の数がいくつになるかを計算するものです。
	計算結果の表示足し算(加法)／引き算(減法)／掛け算(乗法)／割り算(除法)の使い方を説明