フィボナッチ数（再帰）
フィボナッチ数（再帰）
このレッスンで分かること
- フィボナッチは
2 つの基底ケースを持つ- 素朴な再帰版の計算量は
O(2^n)(実際は黄金比の n 乗) ですフィボナッチ数は「直前 2 つの数を足して次の数を作る」数列です
フィボナッチ数 とは
fib(n) = fib(n - 1) + fib(n - 2)を再帰で実装する。2 つの基底ケースが必要なパターンを学ぶ。
フィボナッチ数 は「直前 2 つの数を足して次の数を作る」数列です。具体的には fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, fib(5) = 5, fib(6) = 8 … と続きます。これは植物の枝分かれや、黄金比など、自然界にも顔を出す不思議な数列です。
フィボナッチは
2 つの基底ケースを持つ。階乗より一段だけ複雑な、典型的な再帰パターンだ。
本レッスンでは、この数列を 再帰 で計算する関数を書きます。前回の factorial と違うのは、基底ケースが 2 つあり、再帰呼び出しも 2 回あることです。
数学的な定義
フィボナッチは数学では次のように定義されます。
fib(0) = 0fib(1) = 1fib(n) = fib(n - 1) + fib(n - 2)(n >= 2)
この定義をそのままコードに落とせば、それが 再帰実装 になります。Python ならこうです。
Python
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)if n <= 1: return n の 1 行で fib(0) = 0 と fib(1) = 1 の両方をまとめて表現できます。これは小さなテクニックですが、覚えておくとコードが短くなります。
再帰木 (recursion tree)
fib(5) を計算すると、内部で何回再帰が呼ばれるでしょうか。Mermaid で 再帰木 を描いてみます。
図のポイント (テキスト併記)
fib(3)が 2 回、fib(2)が 3 回呼ばれていることが分かります
fib(3) が 2 回、fib(2) が 3 回呼ばれていることが分かります。再帰 が枝分かれするたびに、同じ計算を何度も繰り返す 重複計算 が発生する、というのが素朴な再帰版フィボナッチの弱点です。
計算量はどのくらい？
素朴な再帰版の計算量は O(2^n) (実際は黄金比の n 乗) です。n = 40 あたりでもう数秒かかるレベルになります。
同じ計算を何度もやり直す
重複部分問題を持つ問題は、メモ化や動的計画法で高速化できる。
本レッスンでは 素朴な再帰 のみを扱います。メモ化 の話は第 6 章 (動的計画法) で詳しく扱うので、まずは「再帰で書ける」状態を体に染み込ませてください。
JavaScript / Java での書き方
JavaScript
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}Java
public class Solution {
public static int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
}どの言語でも、コードはほぼ写経できます。再帰 の表現はそれだけ言語を超えて共通している、ということです。
よくある間違い
if n <= 1: return 1と書くとfib(0) = 1になってしまう。正しくはreturn n。return fib(n - 1)だけにしてしまい、もう片方の+ fib(n - 2)を忘れる。n = 50のような大きな入力でいきなり試すと、何分も待たされる。再帰の遅さを実感する意味ではアリだが、テストはn <= 20程度に。
やってみよう
下の coding 課題で、fib(n) を再帰で実装してください。テストでは 0 から 15 までの値で正しい結果が返るかを確認します。Mermaid の 再帰木 を頭の中で描けるようになるのが目標です。
数列の世界では、
フィボナッチリュカ数トリボナッチなど、漸化式で定義される数列が多数ある。再帰はこれらを最も自然に表現できる道具だ。
Go 版での書き方
Go
func fib(n int) int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2)
}Go でも基本は同じ。シンプルな関数定義に基底ケースと再帰呼び出しを書くだけです。Go の := (短い変数宣言) は今回は不要で、if と return だけで完結します。
フィボナッチの歴史的背景
フィボナッチ は 13 世紀イタリアの数学者 レオナルド・フィボナッチ が、ウサギの繁殖モデルで紹介した数列です。1 つがいのウサギが、毎月新しいつがいを産む、というモデル化が f(n) = f(n - 1) + f(n - 2) の形になります。螺旋 黄金比 植物の葉序 など、自然界の多くの現象とつながりが見つかっており、数学と自然 の橋渡しとして語り継がれてきました。プログラミングの世界でも、再帰 の入門題材として真っ先に登場する 古典中の古典 です。
よくある間違いの追加
素朴な再帰は n が大きいと スタックオーバーフロー になることがあります。n = 1000 程度から危険な言語もあるので、本番でフィボナッチを計算するときは メモ化 か 反復版 (ループ) を使うのが普通です。本レッスンでは n <= 20 までしかテストしないので心配いりません。
よくある質問
Q. 再帰とループはどっちを使うべき？
A. ツリー構造や分割統治（merge sort, BST 走査）は再帰が自然で読みやすくなります。シンプルな反復処理はループが速くスタックも消費しません。再帰深さが配列長に比例する場合、スタックオーバーフローのリスクがあるため気をつけてください。
Q. 再帰のベースケースを忘れるとどうなる？
A. 無限再帰になりスタックオーバーフローします。最初の 1 行目に if (base) return; を書く習慣を付けると安全です。Python は sys.setrecursionlimit で上限を変えられますが、根本的にループに書き換える方が安定します。
Q. 再帰を高速化する方法は？
A. 同じ引数で再計算しているなら memoize（メモ化）で結果をキャッシュします。Python は functools.lru_cache、Java/JS は HashMap で実装します。フィボナッチを memo 付きにすると指数 O(2ⁿ) から線形 O(n) に劇的に高速化します。
次のレッスン
次は 累乗（再帰） で、pow(base, exp) を分割統治で高速に計算する方法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- フィボナッチ の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. フィボナッチ とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 関数
fib(n)を実装し、整数値を返す - for / while を使わず、必ず再帰で実装する
- n <= 1 の場合は n をそのまま返す (2 つの基底ケースをまとめる)
入出力例
test-cases.txt
fib(0) → 0
fib(1) → 1
fib(2) → 1
fib(6) → 8
fib(10) → 55
fib(15) → 610