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

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
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のソースコード解説

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

003
	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メソッドを呼んでおり、これが再帰処理です。

018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
	// メイン
	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 );

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

以上です。

次のコンテンツ

配列を使ったフィボナッチ数列を出力するプログラムを作ってみませんか?

2021.03.09

前のコンテンツ

自然界の現象に数多く出現するフィボナッチ数列のプログラムを作ってみませんか?

2017.01.23

関連コンテンツ

数学に関係するJavaのメソッドやソースコードなどを紹介しています。

2022.10.25

自然界の現象に数多く出現するフィボナッチ数列のプログラムを作ってみませんか?

2017.01.23

配列を使ったフィボナッチ数列を出力するプログラムを作ってみませんか?

2021.03.09

自然界に現れる黄金角について解説しています。興味のある方は是非ご覧ください。

2020.03.23

デザインなどに使われる最も美しい比率について解説しています。

2020.03.23

長方形を使って黄金比を計算する方法を説明しています。

2023.02.15

長方形の分割で、白銀比を計算する方法を説明しています。

2023.11.06

繰り返し処理を使ったJavaのソースコードサンプルを紹介しています。

2020.03.23

基本的な計算である足し算(加法)/引き算(減法)/掛け算(乗法)/割り算(除法)を行うプログラム作成。

2020.03.23

画像フォーマット形式・色・大きさ・傾きなどの変更、特定の図形(文字・記号など)を見つけたり、取り出したりする画像処理について詳しく解説。

2015.11.29

日本で使われてきた伝統文様「和柄」について解説しています。

2022.07.27

プログラミング、ITに関する用語をまとめています。

2022.10.17

条件式を判断して処理を分岐する方法を詳しく説明しています。

2023.03.20

メソッドを抜けるときに使用するreturn文について説明しています。

2020.03.20

変数やクラスに格納されている値をコンソール出力する方法は?

2020.03.23

プログラムの最初に実行されるメソッドは?

2022.12.13

プログラミングで使う変数って何?

2020.03.23

Javaのプログラムを書いてみませんか?プログラムの書き方をくわしく説明しています。

2020.03.23

「Javaソースコード」から実行可能な「オブジェクトコード」に変換する方法をくわしく説明しています。

2020.03.23

同じ型の変数(データ)を複数個まとめて管理するデータの持ちかたがあります。これが配列です。くわしくは、記事をご覧ください。

2016.01.14

ウサギ算(rabbit arithmetic)って何?

2017.02.23

プログラミング言語とは?種類や特徴について説明しています。

2022.08.03

for文で変数名iがよく使われる理由について説明しています。興味のある方は是非。

2022.08.29

メソッドの定義方法を詳しく解説しています。Javaのサンプルソースコードを使った説明もあります。

2020.03.23

広告