Pythonの再帰関数でフィボナッチ数列を求める方法をわかりやすく解説

再帰（リカージョン）を使ってフィボナッチ数列を求めるには、まず値を引数として受け取る fibonacci_recursion という関数を定義します。この関数は、入力値のサイズを小さくしながら自分自身を繰り返し呼び出すことで、最終的な結果を導き出します。

以下に具体的な実装例を示します。

サンプルコード

def fibonacci_recursion(my_val):
   if my_val <= 1:
      return my_val
   else:
      return(fibonacci_recursion(my_val-1) + fibonacci_recursion(my_val-2))
num_terms = 12
print("The number of terms is ")
print(num_terms)
if num_terms <= 0:
   print("Enter a positive integer...")
else:
   print("The Fibonacci sequence is :")
   for i in range(num_terms):
      print(fibonacci_recursion(i))

実行結果

The number of terms is
12
The Fibonacci sequence is :
0
1
1
2
3
5
8
13
21
34
55
89

コードの解説

• 引数として値を受け取る fibonacci_recursion 関数を定義します。
• 再帰を終了させるためのベースケース（基本条件）を設定します。具体的には、引数が1以下の場合はそのまま値を返します。
• それ以外の場合は、my_val-1 と my_val-2 を引数にして自分自身を再帰的に呼び出し、その戻り値を足し合わせます。
• 関数の外側では、求めたい項数（ここでは12項）を変数に格納し、コンソールに表示します。
• 項数が0以下の場合は正の整数を入力するよう促すメッセージを表示し、それ以外の場合はフィボナッチ数列の出力を行います。
• for ループで範囲内の各数値を順番に処理し、そのたびに再帰関数を呼び出して結果を表示します。

注意点：計算量について

シンプルな再帰による実装は理解しやすい反面、同じ計算を何度も繰り返すため、項数が増えると処理時間が指数関数的に増大するという欠点があります。実用的な規模の数列を扱う場合は、メモ化（memoization）を活用するか、ループによる反復処理へ置き換えることで、パフォーマンスを大幅に改善できます。