解説
フィボナッチ数列は、最初の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 番目の数列をリストにまとめて表示してみよう。
コードはあなたの端末の中だけで動きます（サーバーには送られません）。進み具合もこのブラウザに保存されます。
もっと本格的に使うなら
Windows版 InsightPy なら、書いたコードを保存して業務の自動化まで進められます。学習センターはずっと無料です。