Javaプログラミング学習サイト ゆるゆるプログラミング

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()とは?
メソッド メソッドについて解説
ウサギの増え方?-画像

ウサギ算

ウサギ算について解説しています。1対のウサギが1ヶ月毎に1対のウサギを産んでいく場合に、数が月後にウサギの対の数がいくつになるかを計算するものです。

四則演算(足し算/引き算/掛け算/割り算)について-画像

計算結果の表示

足し算(加法)/引き算(減法)/掛け算(乗法)/割り算(除法)の使い方を説明

■新着情報

2021.06.18 変数の初期値 変数に値を代入しないで計算
2021.05.28 短針と長針の角度 短針と長針の角度は?
2021.05.19 各位(くらい)を求める 1の位の値は?10の位は?

■広告

Topへ