Pythonでフィボナッチ数列を再帰関数で実装する方法｜メモ化・O(log n)・再帰上限の実測

フィボナッチ数列は「直前の2項を足す」という定義をそのまま関数にできるため、再帰関数の入門題材として定番です。ただし定義どおりの再帰は、手元のCPython 3.14.6で fib(35) に約3.1秒かかります。この記事では、Pythonでの再帰実装を動かすところから始め、遅くなる理由を呼び出し回数で確かめ、メモ化・反復・高速倍加法で速くする方法を順に示します。Pythonの版によって再帰の上限が変わる点と、C言語・Javaで書くときの整数あふれも実測しています。

まとめ：フィボナッチ数列を再帰関数で書くときの結論

• 書き方：fib(0)=0、fib(1)=1 をベースケースにして return fib(n - 1) + fib(n - 2) と書けば動きます。
• 素朴な再帰は指数時間：呼び出し回数は 2×F(n+1)−1 回で、fib(30) で2,692,537回です。時間計算量は約 O(1.618ⁿ)、再帰の深さは n なので空間計算量は O(n) です。
• 再帰のまま速くするならメモ化：@functools.cache を付けると O(n) になり、fib(35) は0.1ミリ秒未満で終わります。ただし、再帰上限1000・空のキャッシュという測定条件では、CPython 3.9〜3.11はn=498〜499、3.12〜3.14はn=998まででした。呼び出し位置や既存のスタックの深さでも変わります。
• 実務では反復か高速倍加法：forループなら再帰の上限を気にせずに済みます。今回のCPython 3.14.6での測定では、n=100,000と1,000,000で高速倍加法が反復の100倍以上速く、n=1,000,000では約0.16秒でした。
• Python以外では桁あふれに注意：C言語・Javaの32ビット int は F(47)、64ビット long は F(93) であふれます。

フィボナッチ数列の定義と再帰関数の対応

漸化式 F(n)=F(n−1)+F(n−2) の意味

フィボナッチ数列は 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… と続き、各項が直前の2項の和になる数列です。整数列のデータベース OEIS の A000045 では「F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1」と定義されています。教科書によっては F(1)=F(2)=1 から始める流儀もありますが、この場合も n≥1 の添字と値は同じです。この記事は OEIS と同じ F(0)=0 の定義で書きます。

検索で「フィボナッチ関数」と呼ばれるのは、この n を受け取って F(n) を返す関数のことです。漸化式が「自分より小さい n の答え」を使っているので、そのまま再帰関数になります。

ベースケースと再帰ステップの2要素

再帰関数が止まるには、次の2つが要ります。

• ベースケース：それ以上分解しない入力。フィボナッチでは n が0と1のときで、値はそれぞれ0と1です。
• 再帰ステップ：小さい入力で自分を呼び、結果を組み合わせる部分。フィボナッチでは fib(n - 1) + fib(n - 2) です。

ベースケースを書き忘れると、n が負の方向へ減り続けて RecursionError で止まります。呼び出しスタックの仕組みや末尾再帰を言語横断で知りたい場合は、再帰関数とは？自分を呼ぶ関数の仕組みとスタック・末尾再帰・実務判断を解説で扱っています。本記事はフィボナッチ数列に絞ります。

Pythonによるフィボナッチ再帰関数の実装と実行

基本の再帰実装

以下のコードは、nが0以上の整数であることを前提とします。外部入力を使う場合は、呼び出す前に型と範囲を検証してください。漸化式をそのままコードにすると次のとおりです。

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

print(fib(10))  # 55
print(fib(20))  # 6765

定義と1対1で対応しているので、正しさは読めばわかります。問題は速度です。

カウンタによる再帰呼び出し回数の測定

fib(5) は fib(4) と fib(3) を呼び、fib(4) がまた fib(3) を呼びます。同じ引数の計算が何度も繰り返されるので、呼び出し回数を数えると急増がわかります。

calls = 0

def fib(n):
    global calls
    calls += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

for n in (10, 20, 25, 30):
    calls = 0
    fib(n)
    print(n, calls)

回数は 2×F(n+1)−1 に一致します（n=30 なら F(31)=1,346,269 の2倍から1を引いた値）。F(1)=F(2)=1 の定義で n < 3 をベースケースにすると、呼び出し回数は 2×F(n)−1 となり、n=10 で109回です。

Pythonの版ごとの実行時間

カウンタを外した素朴な再帰を、Intel Core i9-9880H 2.30GHz・macOS 26.6.2で各CPythonを使って測定した結果です。掲載値はtime.perf_counter()による各条件1回の測定値で、平均値ではありません。

新しい版ほど速くなっていますが、n が5増えるごとに約10倍という増え方は変わりません。素朴な再帰の遅さは、インタプリタの改良では解消しません。

素朴な再帰の時間計算量と空間計算量

時間計算量は約 O(1.618ⁿ)

呼び出し回数が 2×F(n+1)−1 なので、計算量は F(n) と同じ速さで増えます。F(n) は黄金比 φ≒1.618 の n 乗に比例するため、時間計算量は約 O(φⁿ) です。粗く O(2ⁿ) と書く教材もありますが、上界として正しいだけで、実際の増え方は φⁿ です。n が10増えると φ¹⁰≒123倍になります。

空間計算量は再帰の深さ n に比例

呼び出し回数は膨大でも、同時に積まれる呼び出しフレームは最大で n 個です。fib(n) → fib(n-1) → … → fib(1) と一番深い枝をたどった時点でスタックは n 段になり、戻るたびに解放されます。したがって空間計算量は O(n) で、試験で「スタックによる再帰呼出しの最大空間計算量」を問われたらこれが答えです。Pythonではこの深さに上限があるため、後述の RecursionError につながります。

メモ化による再帰の重複計算の削減

辞書を使った手動メモ化

一度計算した F(k) を辞書に保存し、2回目以降は計算せずに返します。各 k は1回しか計算されないので O(n) です。

memo = {0: 0, 1: 1}

def fib_memo(n):
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

print(fib_memo(100))  # 354224848179261915075

F(100) は 354224848179261915075 で、21桁あります。Pythonの int は桁数に上限がないので、そのまま正確に計算できます。

functools.cache と lru_cache

辞書を自分で管理しなくても、デコレータ1行でメモ化できます。functools.cache は Python 3.9 で追加され、公式ドキュメントでは lru_cache(maxsize=None) と同じものを返すと説明されています。3.8 以前なら @functools.lru_cache(maxsize=None) を使います。

from functools import cache

@cache
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(35))  # 9227465

CPython 3.14.6 での fib(35) は、キャッシュが空の状態から2回測って71マイクロ秒と77マイクロ秒でした。素朴な再帰の3.1秒と比べて約4万倍の差です。キャッシュは関数オブジェクトが生きている間残るので、テストのたびに値を測るなら fib.cache_clear() で消します。

Python 3.11以前は@cache付き再帰の上限が約半分

メモ化しても再帰の深さは n のままです。再帰上限1000のもとで、測定用関数から各実装を呼び、毎回キャッシュを空にして成功した最大のnを測りました。以下の値はこの呼び出し構造での実測値で、モジュール直下や別の関数内から呼ぶ場合には変わります。

3.11 以前では、@cache を付けた関数だけが n=500 の手前で RecursionError になります。C で書かれたキャッシュのラッパーを経由する呼び出しも再帰の深さに数えられ、1段あたり2つ分を消費するためです。Python 3.12 の変更点には「The recursion limit now applies only to Python code」とあり、組み込み関数は別の仕組みで保護されるようになりました。3.12 以降で上限が辞書メモ化と同じ水準に戻ったのはこのためです。

3.11 以前で大きな n を求めたいときは、小さい n から順に呼んでキャッシュを温めておくと、1回の呼び出しで掘る深さが浅くなります。たとえば0から5000まで400刻みで呼べば、fib(5000)（1045桁）まで上限に当たらずに求められました。

Pythonの末尾再帰とスタック使用量の限界

途中の2項を引数で持ち回すと、再帰呼び出しが関数の最後の処理になる「末尾再帰」の形にできます。呼び出しは n+1 回で済むので、時間計算量は O(n) です。

def fib_tail(n, a=0, b=1):
    if n == 0:
        return a
    return fib_tail(n - 1, b, a + b)

print(fib_tail(30))  # 832040

Scheme など末尾呼び出しを最適化する言語では、この形にするとスタックを積まずにループと同じように実行されます。CPython はこの最適化を行いません。Python の作者 Guido van Rossum は2009年のブログ記事「Tail Recursion Elimination」で、スタックトレースが失われることなどを理由に言語へ入れない立場を示しています。今回の測定条件では、CPython 3.12〜3.14の末尾再帰版はn=997まででした。末尾呼び出しでもフレームは省略されず、深さがnに比例する点は素朴な再帰と同じです。Pythonで深い再帰を避けたいなら、末尾再帰に書き換えるより次の反復にします。

再帰を使わずにフィボナッチ数列を求める方法

forループによる反復計算と数列の生成

2つの変数だけを更新していく書き方で、足し算は n 回で、保持する整数は常に2個です。再帰の上限とも無関係です。

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_iter(100))  # 354224848179261915075

数列を先頭から順に使いたい場合は、ジェネレータにすると必要な分だけ取り出せます。

from itertools import islice

def fib_gen():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

print(list(islice(fib_gen(), 12)))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

高速倍加法の恒等式とO(log n)の演算回数

F(2k) = F(k)×(2F(k+1)−F(k))、F(2k+1) = F(k)²+F(k+1)² という恒等式を使うと、n を半分ずつにしながら求められます。行列 [[1,1],[1,0]] の n 乗を繰り返し二乗法で計算する方法と同じ考え方で、掛け算の回数は O(log n) です。再帰の深さも log₂n 程度で、n=1,000,000では再帰呼び出しが20回、最初の呼び出しとn=0のベースケースを含むフレーム数が21個です。

def fib_doubling(n):
    """(F(n), F(n+1)) を返す"""
    if n == 0:
        return (0, 1)
    a, b = fib_doubling(n >> 1)
    c = a * (2 * b - a)   # F(2k)
    d = a * a + b * b     # F(2k+1)
    return (d, c + d) if n & 1 else (c, d)

print(fib_doubling(100)[0])  # 354224848179261915075

どちらも結果は一致しました。n が大きいと F(n) 自体が数十万ビットの整数になり、forループでは1回の足し算も重くなるため差が広がります。n が数千までならforループで十分です。

ビネの公式の浮動小数点実装とn=71の誤差例

一般項 F(n) = (φⁿ−ψⁿ)/√5 を使えば1回の計算で求められます。ただし Python の float（倍精度）で round(phi ** n / sqrt(5)) と計算すると、n=71 で 308061521170130 を返し、正しい値 308061521170129 から1ずれました。整数として正確な値が必要な用途には使えず、近似値や増え方の説明に向く方法です。

大きなnで当たる上限と回避策

RecursionErrorとsetrecursionlimit

再帰の深さが既定の上限1000を超えると RecursionError: maximum recursion depth exceeded になります。sys.setrecursionlimit() で上限を上げられますが、公式ドキュメントはこの上限を C スタックのあふれによるクラッシュを防ぐためのものと説明しており、上げられる最大値はプラットフォームに依存します。上限を上げて再帰を続けるより、反復か高速倍加法に書き換えるほうが確実です。

10進文字列変換の既定4300桁制限とValueError

Python 3.11 以降と、3.10.7 など同時期のセキュリティ修正版では、10進数の文字列変換に桁数の上限があります。既定値は4300桁で、3.10.7 の変更履歴では CVE-2020-10735（巨大な数の変換によるサービス拒否）への対策と説明されています。フィボナッチ数では F(20577) が4300桁でぎりぎり変換でき、F(20578)（4301桁）を print() すると ValueError: Exceeds the limit (4300 digits) for integer string conversion になります。計算自体は成功しているので、表示が必要なら入力サイズと資源消費を制限したうえで、sys.set_int_max_str_digits(5000) のように必要な桁数まで上限を引き上げるか、桁数だけなら bit_length() から見積もります。3.9.6 にはこの上限が無く、F(30000)（6270桁）もそのまま表示されました。

C言語・Javaで再帰を書くときの整数あふれ

再帰の書き方は Python と同じですが、C言語と Java の整数型には上限があります。同じ漸化式を32ビット整数と64ビット整数で計算した結果です（Apple clang 21.0.0・OpenJDK 25.0.4.1で確認）。

Java の int は F(47) で -1,323,752,223 という負の値に化けても例外を出しません。Math.addExact() で足せば ArithmeticException: integer overflow で止まります。C 言語の符号付き整数のあふれは未定義動作なので、結果の値に頼れません。F(93) 以上が要るなら Java は BigInteger、C は多倍長整数ライブラリを使います。C の再帰版は素朴な形のままでは Python と同じく指数時間なので、メモ化か反復にする点も変わりません。

実装方法の使い分け

次の表の計算量は、整数の足し算・掛け算1回を一定時間、整数1個を一定の領域として数えたものです。Pythonの多倍長整数は桁数が増えると1回の演算も重くなるため、実際の時間はこれより速く増えます。forループは n を10倍にすると実行時間が約100倍（0.299秒から29.17秒）になりました。

再帰の学習には素朴な再帰やメモ化を使い、実務で数列を順に生成するならforループ、大きなnの単一項を求めるなら高速倍加法を選びます。採用を避けるべきなのは、素朴な再帰をユーザー入力の n で呼ぶ場面です。n=40では呼び出し回数が331,160,281回に増えます。実行時間は環境に依存し、Webアプリでは設定された制限時間を超えてタイムアウトするおそれがあります。メモ化した再帰も、Python 3.11 以前の実行環境では n=500 前後で落ちるので、入力の上限を決められないなら反復にします。

同じ部分問題を表に記録して再利用する考え方は、動的計画法そのものです。より大きな最適化問題を動的計画法で解くソルバーはDIDPPyとは？動的計画法で最適化問題を解くPythonソルバーの使い方・インストール・比較で、ループ自体を速くする手段はCythonとは？使い方・インストールと型宣言の効果を実測（Cython 3.3対応）で扱っています。計算量の見積もりを含めた業務システムの設計・開発は、フルスクラッチ開発として承っています。

よくある質問

フィボナッチ数列の再帰関数はなぜ遅いのですか？

同じ引数の計算を何度も繰り返すためです。fib(30) の呼び出しは2,692,537回で、回数は 2×F(n+1)−1 と F(n) に比例して増えます。メモ化で各値を1回だけ計算すれば O(n) になります。

Pythonで再帰を使わずにフィボナッチ数列を求めるには？

a, b = b, a + b を n 回繰り返すforループが最も簡単です。数列を順に取り出すならジェネレータ、n が10万を超えるなら高速倍加法を使います。

フィボナッチ数列の計算量はどれくらいですか？

素朴な再帰は時間 O(φⁿ)（φ≒1.618）・空間 O(n) です。メモ化再帰は時間・空間とも O(n)、forループは時間 O(n)・空間 O(1)、高速倍加法は O(log n) 回の掛け算です。

Pythonの再帰の上限はいくつで、変更できますか？

既定は1000で、sys.getrecursionlimit() で確認し sys.setrecursionlimit() で変更できます。上げすぎると C スタックが尽きてクラッシュするおそれがあるため、深い再帰は反復に書き換えるのが安全です。@cache を付けた再帰は、Python 3.11 以前だと n=500 前後で上限に当たります。

フィボナッチ数列の100番目の値はいくつですか？

F(0)=0 から数えると F(100) = 354224848179261915075 です。64ビット整数の上限を超えるため、C言語や Java の long では正しく求められません。Python の int ならそのまま計算できます。

関連記事

• 再帰関数とは？自分を呼ぶ関数の仕組みとスタック・末尾再帰・実務判断を解説
• DIDPPyとは？動的計画法で最適化問題を解くPythonソルバーの使い方・インストール・比較
• Cythonとは？使い方・インストールと型宣言の効果を実測（Cython 3.3対応）
• JavaScriptの探索アルゴリズム｜二分探索・線形探索の実装と計算量で選ぶ基準