Pythonでフィボナッチ数列を実装する方法｜反復処理と再帰処理の2つのアプローチ

フィボナッチ数列は、数学において最も有名な数列のひとつです。計算方法は非常にシンプルで、数列の各項は「直前の2つの数の和」になります。

この数列はプログラミングの世界にも頻繁に登場します。特に、アルゴリズムやループ処理を学ぶ開発者のトレーニング教材としてよく使われています。

このガイドでは、Pythonでフィボナッチ数列をコーディングする方法を解説します。実装方法として、「反復処理（イテレーション）」と「再帰処理」の2つのアプローチを紹介します。

フィボナッチ数列とは？

フィボナッチ数列は、各項が直前の2つの項の合計となる一連の数字です。数列は次のように始まります。

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

新しい数の計算をやめない限り、この数列は無限に続きます。次の数を求めるためのルールは以下の通りです。

x(n) = x(n-1) + x(n-2)

x(n)は数列の次の数、x(n-1)は直前の項、x(n-2)はその前の項を表します。

Pythonでフィボナッチ数列：反復処理アプローチ

まずは、反復処理を使ってフィボナッチ数列を実装する方法から見ていきましょう。

このアプローチでは「while」ループを使用し、特定の条件が満たされるまで次の数を計算し続けます。whileループが1回転するたびにコードが反復されるため、この手法は「反復処理」と呼ばれます。

まず、いくつかの初期値を設定しましょう。

terms_to_calculate = 9
n1, n2 = 0, 1
counted = 0

ここでは4つの変数を宣言しています。

最初の変数は、いくつの値を計算したいかを追跡します。次の2つの変数n1とn2は、数列の最初の2つの項です。これらの初期値を設定しなければ、プログラムはどこから始めればよいのか判断できません。これらの値は、新しい数を計算していく過程で更新されていきます。

最後の変数は、プログラム内で計算済みの項数を追跡するためのものです。

それでは、フィボナッチ数を計算するループを書いてみましょう。

while counted < terms_to_calculate:
	print(n1)
	new_number = n1 + n2
	n1 = n2
	n2 = new_number
	counted += 1

このwhileループは、計算済みの値の数が目的の総数に達するまで実行されます。ループはまずn1の値をシェルに出力し、その後、数列の直前の数とその前の数を足し合わせて次の数を計算します。

続いて、n1の値をn2に入れ替えます。これにより、n1は新しく計算された数の直前の数になります。そして、n2に新しい数を代入します。最後に、+=演算子を使ってcounted変数に1を加算します。

このコードの出力結果は以下の通りです。

0
1
1
2
3
5
8
13
21

プログラムは、フィボナッチ数列の最初の9つの値を正しく計算できました！

Pythonでフィボナッチ数列：再帰的アプローチ

フィボナッチ数列の計算は、再帰処理の完璧なユースケースです。再帰関数とは、問題を解決するために自分自身に依存する関数のことです。

再帰関数は、問題をより小さな問題に分解し、自分自身を呼び出すことで解決します。まず、いくつの数を計算したいかを追跡する変数を初期化しましょう。

terms_to_calculate = 9

このプログラムで初期化が必要なのは、この1つの変数だけです。次に、数列の次の数を計算する関数を作成します。

def calculate_number(number):
	if number <= 1:
		return number
	else:
		return(calculate_number(number-1) + calculate_number(number-2))

この関数は、引数として渡された数が1以下かどうかをチェックします。1以下であれば、計算を行わずにそのまま返します。そうでなければ、calculate_number()関数を2回呼び出して、数列の直前の2つの項の合計を計算します。

最後に、この関数を実行するメインプログラムを書きます。

for number in range(terms_to_calculate):
	print(calculate_number(number))

このループはterms_to_calculateの値と同じ回数だけ実行されます。つまり、このループは9回実行されます。ループ内ではcalculate_number()メソッドを呼び出して数列の次の数を計算し、その結果をコンソールに出力します。

このコードの出力結果は以下の通りです。

0
1
1
2
3
5
8
13
21

出力は先ほどの反復処理の例と同じです。

違いは使用したアプローチにあります。今回は、数列の次の数を計算するために自分自身を呼び出す再帰関数を定義しました。再帰的なアプローチは、ロジックが理解しやすいという理由から、反復的なアプローチよりも好まれることが多いです。

さらに、このコードは反復処理の例よりも大幅に少ない行数で書かれています。しかも、プログラムを動作させるために初期化が必要な変数は1つだけです。反復処理の例では4つの変数を初期化する必要がありました。

まとめ

フィボナッチ数列は、反復処理または再帰処理のどちらのアプローチでも生成できます。

反復処理のアプローチは、whileループを使って数列の次の数を順番に計算していきます。一方、再帰的なアプローチは、自分自身を呼び出して次の数を計算する関数を定義する方式です。

これで、あなたもプロのようにPythonでフィボナッチ数列を計算できるようになりました！