再帰的な関数を用いてフィボナッチ数列を実装します

はじめに

Pythonを用いてフィボナッチ数列を実装します。

フィボナッチ数列とは

フィボナッチ数列は、以下のルールで成り立つ数列です。

1番目の数値は 1
2番目の数値は 1
3番目以降の数値は、直前の2つの数値の和となります。
3番目は 1 + 1 = 2
4番目は 1 + 2 = 3
5番目は 2 + 3 = 5
6番目は 3 + 5 = 8
7番目は 5 + 8 = 13
8番目は 8 + 13 = 21
9番目は 13 + 21 = 34
10番目は21 + 24 = 55

Pythonの再帰回数の上限に注意

Pythonでフィボナッチ数列を再帰関数で実装する場合は、再帰関数の上限（最大再帰数）に注意してください

参考リンク

• https://note.nkmk.me/python-sys-recursionlimit/

コード

import sys

def fibonacci(num : int) -> int:
    """フィボナッチ数列の値を返す

    フィボナッチ数列を返す関数であり、1番目から数え始める。
    0以下の値を受け取った場合は-1で返す

    Args:
        フィボナッチ数列の何番目の値 (1から数え始める)

    Returns:
        指定された番号のフィボナッチ数列を返す
    """

    if num <= 0:
        return -1

    if num == 1:
        return 1

    if num == 2:
        return 1

    return fibonacci(num - 2) + fibonacci(num - 1)


print(f"Recursion upper limit : {sys.getrecursionlimit()}")

# 1番目から10番目までのフィボナッチ数列を出力 (正常ケース)
for i in range(1, 11):
    result = fibonacci(i)
    print(f"[Normal Case] input : {i}, result : {fibonacci(i)}")

# 0番目のフィボナッチ数列を出力 (エラーケース)
print(f"[Error Case] input : {0}, result : {fibonacci(0)}")

# -1番目のフィボナッチ数列を出力 (エラーケース)
print(f"[Error Case] input : {-1}, result : {fibonacci(-1)}")

Recursion upper limit : 1000
[Normal Case] input : 1, result : 1
[Normal Case] input : 2, result : 1
[Normal Case] input : 3, result : 2
[Normal Case] input : 4, result : 3
[Normal Case] input : 5, result : 5
[Normal Case] input : 6, result : 8
[Normal Case] input : 7, result : 13
[Normal Case] input : 8, result : 21
[Normal Case] input : 9, result : 34
[Normal Case] input : 10, result : 55
[Error Case] input : 0, result : -1
[Error Case] input : -1, result : -1

LRUキャッシュを用いて高速化

LRUキャッシュを使用することで、処理を高速化できます

コード

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(num):

    a, b = 1, 1

    for _ in range(1, num):
        a, b = b, a + b

    return a


print(fibonacci(10))
print(fibonacci(100))

55
354224848179261915075