フィボナッチ数列は「前の2つの数を足す」という定義がそのまま再帰関数になるため、再帰の入門題材として最もよく使われます。ただし定義どおりに書いた再帰はnが大きくなると急激に遅くなり、そのまま実務に持ち込むと使いものになりません。この記事では、Pythonでの基本的な再帰実装から、なぜ遅いのかを呼び出し回数の実測で確かめ、メモ化・反復による高速化、そして実装の使い分けまでを、動くコードとともに整理します。
まとめ：Pythonでフィボナッチ数列を再帰実装するときの結論
- 定義：
fib(0)=0、fib(1)=1、fib(n)=fib(n-1)+fib(n-2)。この漸化式をそのまま関数にすると再帰実装になります。 - 素朴な再帰は指数時間：同じ値を何度も計算するため、計算量は約 O(1.618n)。
fib(35)で関数呼び出しは約3,000万回に達し、CPythonで数秒オーダーの時間がかかります。 - 高速化は2択：計算結果を覚えるメモ化（
functools.cache/lru_cache）か、小さい方から積み上げる反復で、どちらも O(n) になります。 - Python特有の注意：Pythonは末尾再帰最適化を行わず再帰の深さに上限（既定1000）があるため、深い再帰は
RecursionErrorになります。学習は再帰、実務は反復かキャッシュ付き再帰が基本です。
フィボナッチ数列と再帰関数の基礎
フィボナッチ数列の定義と漸化式
フィボナッチ数列は 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55… と続く数列で、各項が直前の2項の和になっています。数式で書くと、初項 F(0)=0、F(1)=1 に対して F(n) = F(n-1) + F(n-2)（n≧2）という漸化式で定義されます。この「自分より小さい同じ問題の答えを使う」形が、そのまま再帰関数の構造に対応します。
再帰関数を成り立たせる2つの要素
再帰関数は、関数が自分自身を呼び出す関数です。無限に呼び出し続けないためには、必ず次の2つが必要です。
- ベースケース（終了条件）：それ以上分解しない最小の入力。フィボナッチでは
nが 0 と 1 のとき。 - 再帰ステップ：より小さい入力で自分を呼び、その結果を組み合わせる。フィボナッチでは
fib(n-1) + fib(n-2)。
再帰そのものの仕組み（呼び出しスタックや末尾再帰など）を基礎から確認したい場合は、再帰関数とは何かを仕組みから解説した記事もあわせて参照してください。本記事はフィボナッチ数列という具体題材に絞って掘り下げます。
Pythonでの再帰によるフィボナッチ数列の実装
基本の再帰実装
漸化式をそのままコードに落とすと、次のようになります。ベースケースで n が 0・1 のときはその値を返し、それ以外は2つの再帰呼び出しの和を返すだけです。
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10)) # 55
print(fib(20)) # 6765コードは定義とほぼ一対一で対応しており、正しさが読み取りやすいのが再帰実装の最大の利点です。fib(10) が 55、fib(20) が 6765 と、期待どおりの値を返します。
再帰呼び出しの展開と重複
問題は計算の中身です。fib(5) を求めるとき、内部では fib(4) と fib(3) が呼ばれ、fib(4) はさらに fib(3) と fib(2) を呼びます。つまり fib(3) は複数回、fib(2) はさらに多く重複して計算されます。この「同じ部分問題を何度も解き直す」構造が、次に見る指数時間の正体です。
素朴な再帰が指数時間になる理由
部分問題の重複計算という原因
fib(n) の計算木は、枝分かれのたびにほぼ2倍に増えていきます。深いところにある fib(2) や fib(1) は、何度も何度も同じ値を計算し直します。この重複のため、計算量は入力に対して指数的、具体的には黄金比 φ≒1.618 を底とする約 O(1.618n) になります。nが10増えるごとに、おおよそ100倍以上の計算が必要になる勢いです（φ10≒122倍）。
呼び出し回数を数えて確かめる
抽象的な計算量だけでは実感しにくいので、関数が何回呼ばれたかをカウンタで数えてみます。fib(n) の呼び出し回数は数学的に 2×F(n+1)−1 になり、次のように急増します。
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, 30, 35]:
calls = 0
fib(n)
print(n, calls)| n | fib(n) | 関数呼び出し回数 |
|---|---|---|
| 10 | 55 | 177 |
| 20 | 6,765 | 21,891 |
| 30 | 832,040 | 2,692,537 |
| 35 | 9,227,465 | 29,860,703 |
n=35 で呼び出しは約3,000万回。1つの値を求めるだけでこの回数になるため、素朴な再帰は n が40前後を超えるとまともに終わりません。答え自体は小さな整数なのに、そこへ至る経路が指数的に膨らんでいるのが問題の本質です。
Pythonの再帰上限とスタックの制約
Pythonにはもう一つ、言語固有の壁があります。Pythonは末尾再帰最適化（TCO）を意図的に行いません。再帰呼び出しのたびに呼び出しスタックが積み上がり、その深さには既定で1000という上限が設けられています。フィボナッチの素朴な再帰は深さが最大でも n 程度なので n=1000 付近まで届きにくいものの、深い再帰を書くと RecursionError: maximum recursion depth exceeded が発生します。上限は次のように確認・変更できます。
import sys
print(sys.getrecursionlimit()) # 1000
sys.setrecursionlimit(3000)ただし上限を上げてもスタックメモリを消費し続けるため、根本解決にはなりません。深い再帰が必要な処理は、そもそも再帰ではなく反復で書くのがPythonでの定石です。
メモ化で再帰を O(n) に高速化する
辞書を使った手動メモ化
遅さの原因が「同じ値の再計算」なら、一度計算した値を覚えておけば解決します。この手法をメモ化と呼びます。辞書に計算済みの値を保存し、あればそれを返すだけで、各 fib(n) は一度しか計算されなくなり、計算量は O(n) に落ちます。
memo = {}
def fib(n):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(100)) # 354224848179261915075先ほど数秒かかっていた領域の fib(100) が一瞬で返ります。Pythonの整数は多倍長なので、桁あふれを気にせず大きな項も正確に求められます。
functools.lru_cache と functools.cache を使う
メモ化は自分で辞書を用意しなくても、標準ライブラリ functools のデコレータで実現できます。@lru_cache(maxsize=None) を付けるだけで、引数ごとの戻り値を自動でキャッシュしてくれます。Python 3.9以降なら、上限なしキャッシュの別名である @cache がより簡潔です。
from functools import lru_cache, cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
@cache # Python 3.9 以降。lru_cache(maxsize=None) と同じ
def fib2(n):
if n <= 1:
return n
return fib2(n - 1) + fib2(n - 2)関数本体は素朴な再帰と一字も変わらず、デコレータ1行を足すだけで O(n) になります。読みやすさを保ったまま高速化できるため、再帰の形を残したい場合はこれが第一候補です。
反復とそのほかの求め方
forループによるボトムアップ実装
そもそも再帰を使わず、小さい方から順に足していく反復（ボトムアップ）でも O(n) で求められます。直前の2つの値だけを変数で持ち回すため、メモ化と違って追加のメモリがほぼ不要（O(1)空間）で、再帰上限の心配もありません。
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
print(fib(100)) # 354224848179261915075速度・メモリ・安全性のバランスが最も良く、実務で単純にn番目の値が欲しいだけならこの反復版が扱いやすい選択です。
一般項（ビネの公式）で直接求める
フィボナッチ数には、漸化式を解いた閉じた式（ビネの公式）があります。厳密には F(n) = (φn − ψn)/√5（φ=(1+√5)/2、ψ=(1−√5)/2）ですが、第2項の ψn は0に収束するため、実際には φn / √5 を四捨五入するだけで求められます。ループも再帰も使わず一発で計算できますが、実務では注意が必要です。
import math
def fib(n):
sqrt5 = math.sqrt(5)
phi = (1 + sqrt5) / 2
return round(phi ** n / sqrt5)
print(fib(10)) # 55この式は浮動小数点数で計算するため、n が70程度を超えると丸め誤差で正確な整数からずれます。大きな項を正確に求めたいなら、誤差の出ない反復かメモ化を使うべきで、ビネの公式は「原理的にO(1)で求まる」ことを理解するための位置づけと考えるのが安全です。
実装方法の使い分けと性能比較
ここまでの4つの実装を、計算量・空間・特徴で並べると次のとおりです。
| 実装 | 時間計算量 | 追加メモリ | 特徴 | 使いどころ |
|---|---|---|---|---|
| 素朴な再帰 | 約 O(1.618n) | O(n)（スタック） | 定義に忠実で読みやすいが遅い | 学習・小さいnの説明 |
| メモ化再帰（cache） | O(n) | O(n) | 再帰の形のまま高速化 | 再帰の見た目を保ちたいとき |
| 反復（ループ） | O(n) | O(1) | 速く省メモリ・上限の心配なし | 実務でn番目の値が欲しいとき |
| ビネの公式 | O(1)※ | O(1) | 大きなnで浮動小数点誤差 | 近似・原理理解 |
結論として、フィボナッチ数列で再帰を学ぶ意義は「定義がそのままコードになる」ことを体験する点にあり、素朴な再帰はその教材として最適です。一方で実務でそのまま使うべきではありません。n番目の値を単純に求めるなら反復、どうしても再帰の形を残したいなら @cache を付けたメモ化再帰を選ぶ、というのが明確な判断基準になります。Python自体の実行速度がボトルネックになる数値計算では、CythonでPythonコードをコンパイルして高速化する手法も選択肢になります。
よくある質問
フィボナッチ数列の再帰関数はなぜ遅いのですか？
同じ部分問題（例：fib(2) や fib(3)）を何度も計算し直すためです。計算木が枝分かれのたびにほぼ2倍に増え、計算量は約 O(1.618n) の指数時間になります。メモ化で計算済みの値を覚えれば、各値を一度しか計算しなくなり O(n) に改善します。
再帰を使わずにフィボナッチ数列を求めるには？
直前の2つの値だけを変数で持ち、forループで小さい方から足し上げる反復（ボトムアップ）で求められます。計算量は O(n)、追加メモリは O(1) で、再帰の深さ上限も気にせず済むため、実務ではこの方法が扱いやすい選択です。
大きなnで RecursionError が出るのはなぜですか？
Pythonは再帰呼び出しの深さに既定で1000という上限を設けており、末尾再帰最適化も行わないためです。sys.setrecursionlimit() で上限は上げられますが、スタックメモリを消費し続けるため根本解決にはなりません。深い計算は反復で書き換えるのが定石です。
メモ化と動的計画法の違いは何ですか？
どちらも「部分問題の結果を再利用して重複計算を避ける」点は同じです。メモ化は再帰でトップダウンに解きながら必要な結果だけを記録する方式、動的計画法は反復でボトムアップに表を埋めていく方式を指すことが多いです。フィボナッチではメモ化再帰と反復DPがそれぞれに対応します。より本格的な最適化問題への動的計画法の適用は、動的計画法で最適化問題を解くPythonソルバーDIDPPyの解説が参考になります。
フィボナッチ数列の計算量はどれくらいですか？
素朴な再帰は約 O(1.618n) の指数時間、メモ化再帰と反復はいずれも O(n) の線形時間です。反復は追加メモリが O(1) で済む一方、メモ化はキャッシュ分の O(n) メモリを使います。ビネの公式は原理上 O(1) ですが、浮動小数点誤差のため大きなnでは正確な整数を保証できません。
