解説
フィボナッチ数列は、最初の2項が 0, 1 で、それ以降は直前の2つの和になる数列です。0, 1, 1, 2, 3, 5, 8, 13 … と続きます。
定義をそのまま再帰にできます。
- fib(n) = fib(n-1) + fib(n-2)
- fib(0) = 0, fib(1) = 1（ベースケースが2つ必要）
1回の呼び出しが2回呼び出す「二重再帰」で、計算の枝が木のように広がります。分かりやすい一方、nが大きいと同じ計算を繰り返すため遅くなる注意点も学べます。
書き方
二重再帰: fib(n) = fib(n-1) + fib(n-2)。 ・ベースケースは2つ: fib(0)=0, fib(1)=1。 ・n が大きいと同じ計算を繰り返し遅くなる。
書いて動かす
この回の課題
フィボナッチを再帰で定義し、0〜9 番目の数列をリストにまとめて表示してみよう。
コードはあなたの端末の中だけで動きます（サーバーには送られません）。進み具合もこのブラウザに保存されます。
自分のPCでも続けてみませんか
Windows版 InsightPy は Python を同梱しているので、環境構築なしで同じコードを書いて実行できます。 書いたコードを保存しておけるほか、ステップ実行で変数の変化を1行ずつ確かめられます。 個人の学習や私的な目的でのご利用は、31日目以降も無料です（スクリプトの保存は10本まで）。 このブラウザ版の学習センターも、引き続き無料でお使いいただけます。