Pythonでn番目のフィボナッチ数を求めるプログラム【再帰関数による実装】

はじめに

数値 n が与えられたとき、再帰関数を定義して n 番目のフィボナッチ数を求めます。

例えば、入力が n = 8 の場合、出力は 13 になります。フィボナッチ数列の最初のいくつかの項は次のとおりです。

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

解き方のアプローチ

この問題は、以下の手順で解くことができます。

• solve() 関数を定義します。この関数は引数として n を受け取ります
• n <= 2 の場合、n - 1 を返します（1番目の項が 0、2番目の項が 1 になるようにするため）
• それ以外の場合は、solve(n - 1) + solve(n - 2) を返します

コード例

理解を深めるために、以下の実装例を見てみましょう。

def solve(n):
    if n <= 2:
        return n - 1
    else:
        return solve(n - 1) + solve(n - 2)

n = 8
print(solve(n))

入力

8

出力

13

仕組みの解説

この再帰関数は、フィボナッチ数列の定義「F(n) = F(n-1) + F(n-2)」をそのままコードに表現したものです。solve(8) を呼び出すと、まず solve(7) と solve(6) が呼び出され、さらにそれぞれが自分より小さい引数で自身を呼び出していきます。最終的に n が 2 以下になると n - 1 の値が返され、それらが順に合算されて目的の項が求まります。

注意点：計算量について

このシンプルな再帰実装は分かりやすい反面、同じ計算を何度も繰り返すため、時間計算量は O(2^n) となり、n が大きくなるほど処理が非常に遅くなります。実用的な用途では、メモ化（キャッシュ）を使うか、反復処理によって O(n) まで計算量を改善することをおすすめします。

メモ化による改善例

Pythonの標準ライブラリ functools.lru_cache を使うと、最小限の変更で高速化できます。

from functools import lru_cache

@lru_cache(maxsize=None)
def solve(n):
    if n <= 2:
        return n - 1
    else:
        return solve(n - 1) + solve(n - 2)

n = 8
print(solve(n))  # 出力: 13